Solving Masyu with constraint propagation: an edge model, local patterns, a closure guard, and a uniqueness proof

Masyu (ましゅ / "pearls") in the browser with a single-loop
constraint-propagation solver inside. Three ideas carry it. (1) The
unknowns are edges, not cells — each grid edge is one bit, in the loop or
not; every cell has degree 0 or 2, and a pearl's degree is exactly 2.
(2) Each cell's edges must match one of its legal local patterns — a white
○ runs straight, a black ● turns, a plain cell is unused or bent — and a
black additionally forces the cell one step beyond each arm to run straight.
All strict implications, never guesses. (3) A closure guard kills any loop
that closes before it has swallowed every pearl. Each bundled board is authored
as its own solved loop, so the pearls are read off the answer and can never
drift. Solver-backed puzzle #11.

🌐 Live demo: https://sen.ltd/portfolio/masyu/
📦 GitHub: https://github.com/sen-ltd/masyu

The rules, and the logic that follows

A Masyu grid is R×C. Some cells hold a white ○ or black ● pearl. You
draw one closed loop between orthogonally adjacent cell centres that never
crosses or reuses itself, and:

1. White ○ — the loop passes straight through, and turns in at least one of the two cells immediately before/after it.
2. Black ● — the loop turns here, and runs straight through the cell immediately on each side.

Everything starts with picking the right unknown. For Nonogram or Star Battle
the unknown is a cell; for Masyu the loop is a set of edges, so we make the
edges the unknowns — R*(C-1) horizontal + (R-1)*C vertical, each
UNKNOWN / ON / OFF. A cell's degree (its ON edges) is 0 or 2; a
pearl's is exactly 2. Two strict, guess-free implications fall out.

Local patterns

Every cell's ON edges must equal one of the local patterns allowed for it,
which we enumerate up front:

• Plain: unused (degree 0) or any two edges (degree 2)
• White ○: only its two collinear edges — {left,right} or {up,down}
• Black ●: one horizontal + one vertical — {L,U} {L,D} {R,U} {R,D}

Propagation is then trivial: keep only the patterns consistent with the decided
edges, and whenever the survivors all agree on an edge, force it.

const ok = g.patterns[cell].filter((pat) => {
  for (const e of inc) {
    const inPat = pat.includes(e);
    if (inPat && state[e] === OFF) return false;
    if (!inPat && state[e] === ON) return false;
  }
  return true;
});
if (ok.length === 0) return false;                 // contradiction
for (const e of inc) {                              // agreed on by all → forced
  if (state[e] !== UNKNOWN) continue;
  const anyOn = ok.some((p) => p.includes(e));
  const anyOff = ok.some((p) => !p.includes(e));
  if (anyOn && !anyOff) state[e] = ON;
  else if (anyOff && !anyOn) state[e] = OFF;
}

"White runs straight" and "black turns" are both captured purely by these
patterns. A pearl squeezed against the border with no room to run straight/turn
simply has zero surviving patterns — a contradiction.

Black's "straight on each side" as an edge rule

The half of the black rule about neighbours running straight drops out as an
edge implication: if a black's arm is ON, the edge one cell further along
must be ON too (that neighbour runs straight). If the outer edge is OFF, the
arm can't point that way.

if (state[inner] === ON) {
  if (outer < 0 || state[outer] === OFF) return false;   // no room to run straight
  if (state[outer] === UNKNOWN) { state[outer] = ON; changed = true; }
} else if (state[inner] === UNKNOWN && (outer < 0 || state[outer] === OFF)) {
  state[inner] = OFF;                                     // this arm is impossible
}

White's "turn immediately before/after" depends on a neighbour's shape — it's
non-local, so it's checked at the leaf, not during propagation.

The closure guard

This is the loop-specific crux. A closed cycle can never grow again. So the
instant ON edges form a finished loop, it must already contain every pearl and
every ON edge — any earlier closure would spawn a second loop and is a dead
branch.

for (const [root, hasOpen] of compHasOpen) {
  if (hasOpen) continue;                                       // still growing
  if ((compEdges.get(root) ?? 0) / 2 !== totalOn) return false; // ON edges outside it
  for (let cell = 0; cell < cells; cell++)
    if (g.pearls[cell] !== NONE && find(cell) !== root) return false; // a pearl left out
}

propagate() runs all of this to a fixpoint, then applies the closure guard.

When logic stalls: search that proves uniqueness

Some boards need a guess. The backtracker branches on the edge that extends an
existing loop fragment (a cell already holding one ON edge), tries it ON then
OFF, and lets propagation prune. A complete assignment is accepted only when
isSolution() holds: every cell degree 0 or 2, every pearl rule (including the
non-local white/black neighbour checks), and the ON edges form exactly one
cycle.

export function hasUniqueSolution(puzzle: Puzzle): boolean {
  return solveAll(puzzle, 2).length === 1;
}

The search branches ON/OFF on every undecided edge — a complete
enumeration — pruned only by sound propagation and the closure guard. So the
"unique" it reports is real.

Puzzles are solver-verified, not hand-keyed

Each board is authored as its solved loop plus the pearls that loop earns.
The generator (tools/generate.mts) grows one rectilinear loop from a 2×2 cycle
by repeatedly bumping a straight segment outward into two empty cells (every
bump preserves a single self-avoiding loop), reads every legal white/black
spot off the finished loop, then greedily drops pearls while the solver still
proves a single solution. The tests re-solve every board and assert it recovers
exactly the drawn loop:

expect(hasUniqueSolution(b.puzzle)).toBe(true);
expect(edgeKey(solve(b.puzzle)!)).toBe(edgeKey(b.solution)); // and it's the drawn loop

Same discipline as the Hashiwokakero, Star Battle, Kakuro and Akari entries: ship
your levels through your solver. The bundled boards run 5×5 up to 7×7.

Takeaway

The whole puzzle unlocks once you move the unknown from cells to edges. Then
"white straight / black turn" becomes each cell's local pattern, "black runs
straight on both sides" becomes an edge implication, and "one closed loop"
becomes a closure guard plus a single-cycle check at the leaf. Branch the
undecided edges, prune with sound logic, and the search proves uniqueness while
staying complete. Solver-backed puzzle #11.