Nurikabe, and what replaces candidate enumeration

Nurikabe keeps one idea from Shikaku exactly: a number is the size of the region containing it. It then removes every property that made a Shikaku solver possible. The regions are no longer rectangles, so you cannot list a clue’s candidate shapes. Two of the four rules are global, so no per-cell filter can express them.

What is interesting is what has to arrive in place of the candidate list. Almost none of the reasoning survives; almost all of the architecture does.

The rules, and a board

A grid with numbered clues on some cells. Shade some cells, the sea, so that:

1. Each unshaded region, an island, contains exactly one clue, and its size equals that clue.
2. Islands never touch orthogonally. Diagonal contact is fine.
3. The sea is a single orthogonally connected region.
4. The sea contains no 2×2 fully shaded block.

ISLANDS & SEA · UNIQUE SOLUTION

Nurikabe

Shade the sea. Each number is an island of exactly that many unshaded cells, and islands never touch side by side. The sea is one connected region and never fills a 2×2 square. Tap cycles shade → dot → clear; drag to paint a run.

constructing a layout…

EASY 7×7MEDIUM 8×8HARD 9×9

NEW PUZZLESHOW SOLUTIONCLEAR

Rule 4 is what gives the puzzle its texture. Without it the sea is a background blob; with it the sea is a thin wall winding between islands, and every placement decision propagates a long way. The playable version is at /games/nurikabe/.

Nurikabe is NP-complete, shown by Markus Holzer, Andreas Klein and Martin Kutrib in 2004. Their result is sharper than the bare statement suggests, because the puzzle stays NP-complete when every clue is restricted to 1 or 2. That kills the intuition that large numbers are where the difficulty lives. The hardness is in the connectivity, not the arithmetic.

Why the representation dies

A Shikaku clue of value has at most candidate rectangles, where counts divisors. Small, listable, computable before you start.

A Nurikabe island of size is a polyomino containing the clue. The number of fixed polyominoes of size grows like with , so a clue of 10 has candidates in the hundreds of thousands before you account for placement. The list is not merely large; it is the wrong object to build.

Worth being careful about that constant, since it is doing real work in the argument. That the limit exists follows from supermultiplicativity, plus Fekete’s lemma. (Glue any -omino to any -omino and you get a distinct -omino, so .) Gill Barequet, Günter Rote and Mira Shalah proved in 2016. The upper bound is Klarner and Rivest’s, from 1973, since improved to 4.5252 by Barequet and Shalah. The value 4.06 itself is a numerical estimate, as is the finer asymptotic . For this argument only the lower bound matters, and it is the half that is proved.

And even a complete candidate list would not help, because rules 3 and 4 are global. “The sea is connected” is not a property of any cell or any island; it is a property of the whole board. No filter over per-clue candidates can see it. So the solver has to reason about the grid as a graph, and every rule below is a graph rule.

Four values, not three

Each cell holds one of four states:

• UNKNOWN
• SEA
• NOTSEA: proven white, owner not yet known
• ISLAND(k): white, and owned by clue

NOTSEA is the one worth dwelling on, because it looks redundant and is not. Consider three shaded cells in a 2×2 square. Rule 4 forces the fourth cell white, immediately, with no further reasoning. But nothing about that deduction says which island the cell belongs to. It may be an island whose clue has not been reached by any other rule yet, and on a sparse board it can stay ownerless for many sweeps.

So “white” and “belongs to island ” are two facts, learned at different times, and the state has to be able to hold the first without the second. Collapse NOTSEA into ISLAND(k) and you are guessing an owner the rules have not justified. Collapse it into UNKNOWN and you throw away a deduction you have already paid for, and re-derive it on every sweep.

It is a small decision, but it is why the propagators come out clean. Several of them are about NOTSEA cells: a proven-white cell adjacent to exactly one island joins it; a proven-white cell that no island can still reach is a contradiction; and if proven-white cells outnumber the total remaining growth budget across all islands, the position is dead. None of those rules can be stated at all in a three-valued encoding.

The ladder

As in Shikaku, rules are graded and run cheapest-first to fixpoint, and any change restarts the ladder from the top so an expensive rule never runs on a board a cheap rule could still have advanced.

Grade I: openers and walls. A cell orthogonally adjacent to two different islands must be sea; between two clues at distance two this is the standard opening move. A completed island walls itself, turning all its neighbours to sea. Three sea cells in a 2×2 force the fourth to NOTSEA, and four is a contradiction.

Grade II: reachability. Each clue carries a growth budget . Run a bounded multi-source breadth-first search from island ‘s current cells, at most steps, through UNKNOWN and NOTSEA cells that are not adjacent to a rival island. That marks everything could still absorb. Then any UNKNOWN cell no island can reach is sea.

This is the workhorse, and it is the direct replacement for candidate enumeration. Instead of listing the shapes an island could take and intersecting them, it asks the weaker but far cheaper question of which cells are within reach. Weaker, because a cell being reachable by island does not mean any legal completion of actually contains it. But the rule is only ever used in the negative direction (reachable by nobody, therefore sea), and in that direction the weakness costs nothing. That asymmetry is what makes it work: an over-approximation used only to rule things out is still sound.

Grade III: connectivity. An incomplete island with exactly one cell it could extend into must take it; with none, contradiction. This is articulation reasoning in its cheapest form. The dual rule applies to the sea: separate sea components must eventually join, so a component with a single undecided neighbour extends into it, and a breadth-first search over sea ∪ unknown must still connect every sea cell to every other.

Grade IV: search. Branch a frontier cell sea or not-sea, propagate, backtrack, and count solutions to two under a node budget. The stamp on a generated puzzle records the deepest tier its solution actually requires. That is a stricter claim than size or clue count: it names the hardest thing a solver is obliged to do.

One rule that was quietly wrong

The sea-liberty rule above shipped broken, and it is worth saying how, because the failure is one that unit tests are structurally poor at catching.

The rule loops over sea components, and when a component has exactly one liberty it shades that cell. The original version carried on to the next component. But shading a cell may have merged this component with another, and has certainly changed some other component’s liberty set. So every later iteration was reading a component map that no longer described the board. On boards where that happened, the solver reported contradictions that were not there, and pruned away real solutions.

Every unit test passed. They asserted that the solver reached the intended solution, which it still did: over-pruning removes rival solutions, and the intended one is not a rival. The bug only becomes visible if you ask a question the tests were not asking. Does this deduction hold in every solution? That needs an oracle owing nothing to the solver, so: enumerate all shadings of a 3×3 board by brute force, filter them through the final validator, and check that anything propagation decides agrees with all of them. Three puzzles’ worth of that turned up two soundness bugs.

The fix is one line: return immediately instead of continuing the loop, and let the ladder restart with a fresh component map. Cheap, because restarts are cheap, and the alternative is a rule that invents contradictions.

Generation by repair

The obvious way to generate a board is to place islands and let the rest be sea. It fails almost every time, because rule 4 is a constraint on the sea, and a sea that is whatever happens to be left over is full of 2×2 blocks. You end up rejecting and retrying, with no signal about which placement was to blame.

Inverting it makes validity constructive:

1. Start with an all-sea grid.
2. While any 2×2 all-sea block exists, pick one and turn one of its cells white, choosing a cell whose conversion touches at most one existing island (never merging two), keeps that island under the size cap, and leaves the sea connected. Weight the choice towards extending small islands so sizes spread.
3. When no 2×2 block remains, the layout is valid by construction: the sea is connected because that was a loop invariant, there is no 2×2 block because that was the loop condition, and islands do not touch because they were never merged. Place one clue per island; the values are the sizes.
4. Verify uniqueness by counting solutions to two, grade the result, and keep the best candidate against a difficulty target within a time budget.

The move is to stop treating the 2×2 rule as a filter and start treating it as the loop condition. Each repair strictly reduces the number of violating blocks, so the loop terminates, and everything it does preserves the other three rules. The generator never rejects a layout for a reason it cannot name.

It does occasionally corner itself: every cell of some remaining block is a sea articulation point, so no conversion is legal. The fix is to abandon that layout and start again. Restarts being cheap is not an accident of this puzzle; it is what you buy by making each attempt independent, and it is why the time budget belongs to the whole generation run rather than to any single attempt.

What transferred, and what did not

From the Shikaku solver, unchanged: the graded-ladder architecture, uniqueness as a counting problem, node budgets, difficulty targeting in the generator, and the grade stamp being a claim about the shallowest rung that suffices.

Entirely new, and all of it forced by the loss of enumerable candidates and the arrival of global rules: the four-valued cell state, bounded-BFS reachability with per-island budgets, liberty and articulation forcing, and connectivity accounting run on both the islands and the sea.

That split is the useful thing to notice. The architecture (grade, propagate to fixpoint, count for uniqueness, generate against a target) turned out to be independent of the puzzle. The representation did not survive first contact at all. Which suggests the layers were drawn in about the right place, and that a third puzzle should be able to reuse the frame while replacing the contents again. Slitherlink does exactly that: its constraints live on edges rather than cells, and its connectivity argument runs through the Jordan curve theorem rather than breadth-first search, but the ladder, the oracle and the generator loop are the same ones.

Sources

• Markus Holzer, Andreas Klein and Martin Kutrib, “On the NP-Completeness of the Nurikabe Pencil Puzzle and Variants Thereof”, Proceedings of the 3rd International Conference on FUN with Algorithms, 2004.
• Gill Barequet, Günter Rote and Mira Shalah, “λ > 4: An Improved Lower Bound on the Growth Constant of Polyominoes”, Communications of the ACM 59(7), 2016.
• D. H. Redelmeier, “Counting polyominoes: Yet another attack”, Discrete Mathematics 36, 1981.
• Takayuki Yato and Takahiro Seta, “Complexity and Completeness of Finding Another Solution and Its Application to Puzzles”, IEICE Transactions on Fundamentals E86-A(5), 2003.
• OEIS A001168, fixed polyominoes.
• Nikoli’s own rules for Nurikabe.