The mathematics of Nikoli puzzles
Cell Blocks, Nurikabe and Slitherlink share no rules, but they share a shape: local arithmetic plus one global topological constraint. That split explains where the difficulty lives, why propagation always stops short, and what a puzzle with a well-behaved global constraint would look like.
Cell Blocks, Nurikabe and Slitherlink have nothing in common at the level of rules. One divides a grid into rectangles, one shades a sea around islands, one draws a single closed loop through the gaps between numbers. They are playable at /games/.
Underneath, all three are the same kind of object. Each is a set of local arithmetic constraints attached to the clues, plus exactly one global topological constraint on the whole board. Almost everything interesting about any of them follows from that split, including which parts are easy, which parts are hard, and where a solver has to give up and guess.
The shape
| Local arithmetic | Global topology | |
|---|---|---|
| Cell Blocks | each clue | the regions partition the grid |
| Nurikabe | each clue | the sea is connected, with no 2×2 block |
| Slitherlink | each clue | the on-edges form one closed curve |
The left column is arithmetic on small numbers, and it is entirely local: you can check a clue by looking at the cells around it. The right column cannot be checked by looking anywhere in particular. Connectivity, partition and “one closed curve” are all properties of the configuration as a whole.
That asymmetry is not a coincidence of these three. It is close to what makes a pencil puzzle a pencil puzzle. A grid of purely local constraints is a constraint-satisfaction problem that arc-consistency tends to walk straight through, and it plays like arithmetic homework. The global constraint is what supplies the moment where a solver stares at a board on which no individual clue says anything new.
Why the split is where the difficulty lives
Local constraints have a fixpoint. You apply them until nothing changes, which takes polynomial time, and what you get is the strongest conclusion local reasoning supports. That is the whole of what a propagation loop can do.
A global constraint has no such loop, because it is not a conjunction of things you can check separately. So a solver has three options, and every one of these puzzles uses all three:
Relax it into something local. Slitherlink’s “one closed curve” is relaxed to “every vertex has degree 0 or 2”, which is local and cheap, and gets most of the work done. What survives the relaxation is exactly the failure mode: degree conditions permit several disjoint loops, which is the one thing the real constraint forbids.
Approximate it in the safe direction. Nurikabe’s islands are polyominoes,
and fixed polyominoes grow like
Search. When both of the above have run dry, branch on an undecided variable and propagate again. This is where the exponent lives.
Note what the second option costs. Because the propagator is deliberately weaker than the constraint, it is sound but incomplete: it never asserts anything false, and it routinely fails to assert something true. Incompleteness is not a defect to be fixed. It is the price of a polynomial-time step, and given that these puzzles are NP-complete, a complete polynomial propagator would be a rather larger result than a puzzle generator.
The parity trick, which is the prettiest case
Slitherlink’s global constraint has more structure than “connected”, and one consequence is worth pulling out.
A closed curve in the plane divides it into inside and outside. So colour the
faces of the grid, including the outer face, with two colours. An edge is on
exactly when the two faces it separates differ. That is the Jordan curve theorem
doing combinatorial work: the loop constraint becomes a two-colouring of the
dual graph, and the puzzle becomes a question about a
The payoff is that you can now reason about faces whose relative colour is known without knowing either colour. Union-find with a parity bit tracks exactly this: merge two faces as same or different, and derive edges wherever a clue pins the relation down. Deductions become available that no amount of local edge-counting would reach, because they are statements about a relation rather than about a value.
The same move is why “how many disjoint loops” is a hard question and “is this edge inside or outside” is a tractable one. Changing what you take as the variable can convert a global constraint into a local one on a different graph.
Uniqueness is a counting problem, and it is the expensive half
Solving these puzzles is not what a generator does. A generator has the solution already; it built it. What it needs to know is whether the solution is the only one, and that is a different problem.
The implementation is always the same: count solutions with an early exit at two. Two is as informative as two thousand, and a great deal cheaper.
There is a matching piece of theory. Given one solution, is there another? That is the Another Solution Problem, introduced by Nobuhisa Ueda and Tadaaki Nagao in 1996 and generalised by Takayuki Yato and Takahiro Seta in 2003, who proved Slitherlink ASP-complete. The content of ASP-completeness is that the free head start is worth nothing: holding a solution does not help you find a second, so the generator’s advantage over a player is smaller than it feels.
Which is why the sane way to build a puzzle is by deletion. Draw a valid solution, read off every clue, then repeatedly try removing a clue and keep the removal only if uniqueness survives. Removal is a veto rather than a search: you are confirming that a property still holds rather than hunting for a configuration that has it. Each individual check is expensive, and there is no shortcut, but you always know what you are doing and why the last step failed.
Hardness results, used honestly
Nurikabe is NP-complete, shown by Markus Holzer, Andreas Klein and Martin Kutrib in 2004, and their version is sharper than the bare statement: it holds even when every clue is a 1 or a 2. That kills the intuition that big numbers are where the difficulty lives. Slitherlink is NP-complete too, from Yato in 2000.
It is tempting to let this explain why a generator is slow. It does not. NP-completeness is an asymptotic statement and a 7×7 board is a fixed size, so it proves nothing whatever about the running time of any particular program. What it does tell you is that no clever reformulation is waiting to be found, which is worth knowing before spending a week looking for one. That is the practical content of a hardness result, and it is smaller than it is usually made to sound.
What happens when the global constraint is well behaved
Every puzzle above has a global constraint that is hard in the worst case. It is natural to ask what a puzzle would be like if it were not.
Take a grid where some cells are sources with a supply, some are sinks with a
demand, and the player draws arrows so that flow is conserved at every other
cell. The global constraint is now conservation, which is linear. The constraint
matrix of a flow problem is a network matrix, network matrices are totally
unimodular, and a totally unimodular system has an integral linear relaxation.
So the question “can this partially filled board still be completed?” is a
feasibility question about a
That is a genuinely different object. In Nurikabe or Slitherlink there is no way to ask a partial board whether it is still alive without, in effect, solving it. Here there is, which means a perfect hint oracle and a solver that never has to guess wrongly about feasibility.
The hardness does not vanish; it moves. Feasibility becomes easy and uniqueness stays hard, because counting the flows consistent with a board is a different problem from finding one. The generator’s loop, the counting to two and the difficulty ladder all still have work to do. It is the solver’s relationship to search that inverts.
I am building this one next, and the interest is precisely that it is the case where the pattern above should break in a predictable place. A prediction that is then checked is worth more than three examples that agreed.
The honest limit
Three puzzles is not a theory. They come from one publisher, they are all grids with integer clues and a uniqueness guarantee, and I picked the second and third partly because they looked like interesting distances from the first. The local-plus-global reading fits them well, and it fits a good deal of Nikoli’s catalogue on inspection, but “fits on inspection” is where a pattern lives before anyone has tried to break it. The fourth puzzle is chosen to try.
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.
- Takayuki Yato, “On the NP-completeness of the Slither Link Puzzle”, IPSJ SIG Notes AL-74, 2000.
- 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. The Another Solution Problem itself is due to Nobuhisa Ueda and Tadaaki Nagao, “NP-completeness results for NONOGRAM via parsimonious reductions”, 1996.
- 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.
- Alan Hoffman and Joseph Kruskal, “Integral Boundary Points of Convex Polyhedra”, in Linear Inequalities and Related Systems, 1956, for the total unimodularity behind the integral relaxation.
- David Gale, “A theorem on flows in networks”, Pacific Journal of Mathematics
7(2), 1957, for feasibility of a