Solving Nurikabe with constraint propagation: three-valued cells, a reachability flood, and a uniqueness proof

Nurikabe (ぬりかべ / "plaster wall") in the browser with a
constraint-propagation solver inside. Every cell is white (part of a
numbered island) or black (the sea), and the solver keeps a
three-valued cell — UNKNOWN / WHITE / BLACK — running sound
deductions to a fixpoint before it ever guesses. Four rules feed each other:
the pool rule (no 2×2 all-black), the sealed island (a white region the
size of its clue seals its border), the merge / over-size check, and the
one that does the heavy lifting — a reachability flood that expands every
clue outward and blacks out any cell no clue can still reach. Each bundled
board is authored as its own solved sea, so the clues are read off the answer
and can never drift. Solver-backed puzzle #12.

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

The rules, and the logic that follows

A Nurikabe grid is R×C with some cells carrying a number. A finished board
paints every cell white or black so that:

1. each island is one orthogonally-connected white block holding exactly one number, and its size equals that number;
2. islands never touch orthogonally (a black cell always separates them);
3. all black cells form one connected sea with no 2×2 pool.

The unknown here is simple — one bit per cell, white or black — but the rules
tangle connectivity (islands and sea) with counting (island sizes) with a
local shape ban (the 2×2 pool). We model the cell three-valued (UNKNOWN
until decided) and shrink it with strict, guess-free deductions.

The pool rule and sealed islands

Two are immediate. No 2×2 window may be all black, so three blacks force the
fourth white, and four blacks is an instant contradiction. And a white region
whose size already equals its clue is finished — every unknown cell touching
it becomes sea:

if (cells.length === clue) {
  for (const cell of cells)
    for (const nb of g.nbrs[cell])
      if (state[nb] === UNKNOWN) { state[nb] = BLACK; changed = true; }
}

The same region scan rejects two clues merged into one region, or a region grown
past its number.

The reachability flood

This is the crux. A cell can be white only if some clue's island could still
grow to include it. So flood every clue outward through unknown cells, spending
one unit of its remaining budget (clue − current size) per unknown cell
entered, and black out every cell no flood reaches:

for (const { id, cells, clue } of clued) {
  const budget = clue - cells.length;          // cells this island may still add
  // BFS from the island, cost = unknown cells spent; mark everything ≤ budget
  ...
}
for (let i = 0; i < g.N; i++) {
  if (reach[i]) continue;
  if (state[i] === UNKNOWN) { state[i] = BLACK; changed = true; }   // unreachable → sea
  else if (state[i] === WHITE && region[i] === -1) return false;    // stranded island
}

The subtle part is soundness. For "unreachable ⇒ black" to be safe, the
flood must never miss a genuinely reachable cell — its reach set has to be a
superset of the truth. So the flood is deliberately generous: it lets
orphan white cells be crossed for free and ignores the finer "can't sit next to
another island" refinement. Over-counting reach only ever leaves fewer cells
to black out, so every cell it does black is provably sea. Being generous is
what makes the deduction correct.

propagate() runs the pool rule, sealing, the region checks and the flood to a
fixpoint, returning false the instant any rule contradicts.

When logic stalls: search that proves uniqueness

Some boards need a guess. The backtracker branches on the most constrained
unknown cell (the one touching the most already-decided cells), tries it BLACK
then WHITE, and lets propagation prune. A complete assignment is accepted only
when isSolved() holds: every island exact and clued, the sea one connected
region, and no 2×2 pool.

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

solveAll branches BLACK/WHITE on undecided cells — a complete
enumeration — pruned only by sound propagation. It stops at two solutions, so
the "unique" it reports is real.

Puzzles are solver-verified, not hand-keyed

Each board is authored as its solved grid. The generator
(tools/generate.mts) is sea-first: it grows one connected sea by a random
walk that never completes a 2×2 pool, then reads the leftover white
components off as islands — so connectivity and pool-freeness hold by
construction, not by rejection sampling. It drops one number per island and
keeps the clue set only if the solver proves a single solution. The tests
re-solve every board and assert it recovers exactly the drawn sea:

expect(hasUniqueSolution(b.puzzle)).toBe(true);                 // exactly one answer
expect(Array.from(solve(b.puzzle)!)).toEqual(                  // and it's the drawn one
  Array.from(b.solution),
);

One tuning note worth its own line: raising the sea's coverage produces
smaller, more numerous islands, which means more clues, which makes a
single-clue-per-island board far likelier to be uniquely solvable — and cheaper
to verify. That one knob was the difference between the 10×10 generating in
seconds versus not at all. Same discipline as the Masyu, Hashiwokakero, Star
Battle, Kakuro and Akari entries: ship your levels through your solver. The
bundled boards run 5×5 up to 10×10.

Takeaway

Nurikabe looks like a shading puzzle but it's really a reachability puzzle.
Once the unknown is a three-valued cell, "no pool" and "sealed island" are cheap
local rules, "one connected sea" is a leaf check, and the real deductions come
from a generous flood that blacks out everything no clue can claim — sound
precisely because it over-counts. Branch the most-constrained cell, prune with
that logic, and the search proves uniqueness while staying complete.
Solver-backed puzzle #12.