Masyu

Masyu draws a single closed loop through pearls. The grid is a rectangle of cells; some cells contain a pearl, either white (an open ring) or black (a filled disk). The solver must draw a single non-self-crossing closed loop on the grid that passes through the centre of every pearl, plus possibly some empty cells, subject to two pearl-specific rules.

• At a white pearl, the loop passes straight through (horizontally or vertically), but in at least one of the two cells immediately before or after, the loop turns.

• At a black pearl, the loop turns (a right-angle bend), and the loop passes straight through both of the cells immediately before and after the pearl.

The puzzle was published by Nikoli in $1999$ in Puzzle Communication Nikoli; masyu translates to “evil influence” in Japanese, with the pearls (shinju) as the visual hook. The puzzle is also marketed in English as White Pearls and Black Pearls and occasionally as Pearl Loop. Among Nikoli loop puzzles it is arguably the most photogenic; the rules are local enough to admit elegant hand-solving and the resulting loops are visually striking.

The model reuses the AddCircuit-with-self-loops machinery from Slitherlink (Chapter $9$), but here the loop runs on cell centres rather than lattice corners, so the nodes of the circuit graph are the cells themselves and the edges connect orthogonally adjacent cells. The pearl rules become local constraints on each pearl cell about the combinations of incident edges and the turn behaviour of neighbouring cells.

Rules and a small instance

A Masyu puzzle is an $R \times C$ grid. Some cells carry a pearl. The solver must place a single closed loop on the grid such that:

1. Every cell is either on the loop (with two of its four edges to neighbouring cells in the loop) or off the loop (with zero loop-edges).

2. Every pearl cell is on the loop.

3. At a white pearl, the two loop edges are collinear (both horizontal or both vertical), and at least one of the two cells in that direction is itself a turn (its two edges are perpendicular).

4. At a black pearl, the two loop edges are perpendicular (a turn), and the cell on each of the two active sides is straight through.

5. The loop is a single non-self-crossing closed curve.

Figure 14.1 is puzzle $1$ from the janko.at Masyu archive, a $6 \times 6$ instance by Warai Kamosika with two black and four white pearls.

The programming model

The variables are edge booleans on the cell-graph, plus, for each cell, indicator variables describing the local pattern of incident loop-edges.

• $h_{r, c}$ is the edge between cells $(r, c)$ and $(r, c + 1)$, for $0 \le r < R$ and $0 \le c < C - 1$.

• $v_{r, c}$ is the edge between cells $(r, c)$ and $(r + 1, c)$, for $0 \le r < R - 1$ and $0 \le c < C$.

For each cell define three indicator booleans:

• $\ell_{r, c}$, true iff the cell is on the loop (sum of incident edges $= 2$, otherwise $= 0$).

• $\sigma^h_{r, c}$, true iff the cell is straight horizontal: both $E$ and $W$ edges are in the loop, both $N$ and $S$ are not.

• $\sigma^v_{r, c}$, true iff straight vertical.

• $\tau_{r, c}$, true iff the cell turns (perpendicular edges).

If $\ell_{r, c}$ is true, exactly one of $\{\sigma^h_{r, c}, \sigma^v_{r, c}, \tau_{r, c}\}$ is true.

Pearl rules

For a white pearl at $(r, c)$: $$\sigma^h_{r, c} \vee \sigma^v_{r, c}.$$ If $\sigma^h_{r, c}$ is true, at least one of $\tau_{r, c-1}, \tau_{r, c+1}$ is true. If $\sigma^v_{r, c}$ is true, at least one of $\tau_{r-1, c}, \tau_{r+1, c}$ is true.

For a black pearl at $(r, c)$: $\tau_{r, c}$. For each active incident edge, the cell on the other side of that edge is straight in the same direction. For example, if the $E$ edge of $(r, c)$ is in the loop, then $(r, c + 1)$ is straight horizontal.

Single-loop constraint

Same as Slitherlink: AddCircuit on a directed-arc graph where each undirected edge contributes two arcs (one per direction) summing to the edge variable, and each vertex (cell) has a self-loop arc enabled iff $\ell_{r, c}$ is false.

A solver in fifty lines

from ortools.sat.python import cp_model

def solve_masyu(R, C, pearls):
    """pearls: {(r, c): 'w' | 'b'}.  Returns edge dicts."""
    m = cp_model.CpModel()
    h = {(r, c): m.NewBoolVar("")
         for r in range(R) for c in range(C-1)}
    v = {(r, c): m.NewBoolVar("")
         for r in range(R-1) for c in range(C)}

    def edges(r, c):
        e = {}
        if c > 0:    e['W'] = h[(r, c-1)]
        if c < C-1:  e['E'] = h[(r, c)]
        if r > 0:    e['N'] = v[(r-1, c)]
        if r < R-1:  e['S'] = v[(r, c)]
        return e

    on_loop, turn, sh, sv = {}, {}, {}, {}
    for r in range(R):
        for c in range(C):
            e = edges(r, c)
            elist = list(e.values())
            ol = m.NewBoolVar("")
            m.Add(sum(elist) == 2).OnlyEnforceIf(ol)
            m.Add(sum(elist) == 0).OnlyEnforceIf(ol.Not())
            ns = sum(e[k] for k in ('N','S') if k in e)
            ew = sum(e[k] for k in ('E','W') if k in e)
            hh = m.NewBoolVar("")
            m.Add(ew == 2).OnlyEnforceIf(hh)
            m.Add(ew <= 1).OnlyEnforceIf(hh.Not())
            vv = m.NewBoolVar("")
            m.Add(ns == 2).OnlyEnforceIf(vv)
            m.Add(ns <= 1).OnlyEnforceIf(vv.Not())
            tt = m.NewBoolVar("")
            m.AddBoolAnd([ol, hh.Not(), vv.Not()]
                         ).OnlyEnforceIf(tt)
            m.AddBoolOr([ol.Not(), hh, vv]
                        ).OnlyEnforceIf(tt.Not())
            on_loop[(r,c)] = ol
            turn[(r,c)] = tt; sh[(r,c)] = hh; sv[(r,c)] = vv

    def need_turn(flag, neighbours):
        ts = [turn[n] for n in neighbours if n in turn]
        if len(ts) == 2:
            m.AddBoolOr(ts).OnlyEnforceIf(flag)
        elif ts:
            m.Add(ts[0] == 1).OnlyEnforceIf(flag)

    def black_side(edge, side_cell, side_dir):
        target = sh if side_dir == 'h' else sv
        m.Add(target[side_cell] == 1).OnlyEnforceIf(edge)

    for p, k in pearls.items():
        m.Add(on_loop[p] == 1)
        r, c = p
        if k == 'w':
            m.AddBoolOr([sh[p], sv[p]])
            need_turn(sh[p], [(r, c-1), (r, c+1)])
            need_turn(sv[p], [(r-1, c), (r+1, c)])
        else:
            m.Add(turn[p] == 1)
            e = edges(r, c)
            if 'N' in e: black_side(e['N'], (r-1, c), 'v')
            if 'S' in e: black_side(e['S'], (r+1, c), 'v')
            if 'E' in e: black_side(e['E'], (r, c+1), 'h')
            if 'W' in e: black_side(e['W'], (r, c-1), 'h')

    arcs = []
    vid = lambda r, c: r * C + c
    for (r, c), e in h.items():
        f = m.NewBoolVar(""); b = m.NewBoolVar("")
        m.Add(f + b == e)
        arcs.append((vid(r, c), vid(r, c+1), f))
        arcs.append((vid(r, c+1), vid(r, c), b))
    for (r, c), e in v.items():
        f = m.NewBoolVar(""); b = m.NewBoolVar("")
        m.Add(f + b == e)
        arcs.append((vid(r, c), vid(r+1, c), f))
        arcs.append((vid(r+1, c), vid(r, c), b))
    for p in on_loop:
        arcs.append((vid(*p), vid(*p), on_loop[p].Not()))
    m.AddCircuit(arcs)

    s = cp_model.CpSolver()
    s.Solve(m)
    H = {k: s.Value(v) for k, v in h.items()}
    V = {k: s.Value(v) for k, v in v.items()}
    return H, V

The toy of Figure 14.1 solves uniquely in about $6$ milliseconds.

A hard instance

Figure 14.3 is puzzle $80$ from the janko.at Masyu archive, a $16 \times 16$ instance by Grant Fikes (the prolific puzzle blogger at mathgrant). It carries $54$ pearls, several of them in tightly clustered runs that force long sequences of black-pearl-and-straight cells. The same solver code returns the unique loop in about $65$ milliseconds.

Sources. Masyu was published by Nikoli in $1999$. The toy is puzzle $1$ from the janko.at Masyu archive (Warai Kamosika); the hard instance is puzzle $80$ (Grant Fikes). Friedman established NP-completeness of Masyu in $2002$ in a self-published note (erich-friedman.github.io). The CP modelling pattern of AddCircuit-with-self-loops is the same as in Chapter $9$.