Slitherlink is a two-colouring puzzle wearing a loop costume
The Jordan curve theorem turns a puzzle about drawing one closed loop into a puzzle about colouring cells inside or outside, which makes it the dual of Nurikabe and hands the whole connectivity toolkit over unchanged.
Slitherlink asks you to draw a single closed loop on a lattice so that each numbered cell has exactly that many loop edges on its border. Stated that way it sounds like a puzzle about curves, and the obvious solver reasons about curves: track chains of edges, join them up, make sure you end with one.
That solver works and it is not the interesting one. There is an exact restatement in which no loop appears at all, only a two-colouring of cells, and it turns a topological constraint into a connectivity constraint of the kind Nurikabe already needed. The loop is a costume.
The rules, and a board
A
In graph terms: a subgraph of the lattice in which every vertex has degree 0 or 2, the on-edges form exactly one cycle, and the incidence counts match the clues. As always, a published puzzle has exactly one solution.
Slitherlink
Draw one closed loop along the dots. Each number counts the loop edges around its cell, and the loop never crosses or branches. Tap an edge to cycle line → ✕ → clear; drag to continue a line.
The playable version is at /games/slitherlink/. Slitherlink is a Nikoli original, first published in 1989, as are Nurikabe and Shikaku, the subjects of the two posts either side of this one. Sudoku, the one everybody knows, is the outlier: Nikoli imported and renamed it. In English the puzzle also turns up as Loop the Loop, Fences and Takegaki.
The easy half: degree
“Every vertex has degree 0 or 2” is the local skeleton of “loop”, and it does
most of the cheap work. Two on-edges at a lattice point kill the other two. A
point with one on-edge and one undecided edge forces that edge on. Three
on-edges is a contradiction. Alongside it sits the clue rule, which is just
counting: for a clue
Between them these two rules solve easy boards outright. They cannot see the loop, though, only its skeleton. Nothing so far distinguishes one closed loop from three separate ones.
The deep half: the Jordan curve theorem
A simple closed curve in the plane divides it into an inside and an outside. That is the Jordan curve theorem, famous for being obvious and hard to prove. For Slitherlink it yields an exact reformulation:
Give every cell (plus one virtual outer cell surrounding the board) a colour, IN or OUT, with the outer cell OUT. An edge is on the loop if and only if its two adjacent faces have different colours. A clue
then says: exactly of this cell’s four face-neighbours have the opposite colour.
Read that twice, because everything follows from it. The loop is no longer a thing you track. It is a derived quantity, the boundary between two colour classes, and every statement about edges becomes a statement about cells.
Above: the shaded cells are IN, and the loop is exactly the set of edges with one shaded side. The clues follow: the top-left cell has two neighbours of the opposite colour, so it reads 2; the bottom-right has none, so it reads 0. Below: colour a 2×2 block diagonally and all four edges at its centre turn on, so the loop meets itself. This is the whole no-pinch condition, and it is local.
Now the single-loop condition, which the degree rules could not express, becomes something Nurikabe’s machinery already handles: the IN region must be connected and simply connected: connected, and with no holes. Equivalently: IN is connected, OUT is connected, and the boundary between them never pinches to a point.
That last condition has a crisp local form, which is the happy part. A pinch happens exactly when a 2×2 block of faces is coloured diagonally (IN and OUT on one diagonal, OUT and IN on the other), because then all four edges at the shared lattice point separate differing faces, so all four are on, and the loop touches itself. So “no pinch” is not a global topological check. It is a rule about 2×2 blocks, and Nurikabe’s rule was also about 2×2 blocks.
The two puzzles are dual cousins. Nurikabe shades cells and asks for a connected sea with no 2×2 block; Slitherlink colours cells and asks for a connected, hole-free inside with no 2×2 diagonal. Single-liberty forcing, unreachable-region contradictions, articulation arguments: all of it transfers, and none of it had anything to do with loops.
Parity, and free theorems
The dual view hands over a family of results that cost nothing to state and are awkward to see from the loop side. They all descend from one fact: a closed curve crosses any other closed curve an even number of times.
- Row and column crossings. Scan across any row of cells. The number of vertical on-edges you cross is even, because the loop must leave as often as it enters.
- Walk parity. More generally, take any closed walk that steps from cell to neighbouring cell and returns to where it started, counting the outside as one more cell. The number of on-edges it crosses is even.
The row rule is the special case where the walk leaves the outside, runs along the row, and comes back, which is why only the vertical edges get counted.
It is worth being careful about what this does not say, because the tempting generalisation is false. It is not true that any set of cells has an even number of on-edges around its boundary: a cell clued 3 is a counterexample all by itself. The parity argument needs a closed walk through cells, and the boundary of a region is a set of edges, not a walk.
In the colouring even the true version stops being a theorem and becomes bookkeeping. A crossing is a colour change, and a walk that returns to its starting cell must have changed colour an even number of times to get back to the colour it started on. An argument that needs care on the loop side is a triviality on the dual side, which is the usual sign that the dual side is the right place to stand.
One extra bit per node
To exploit the colouring you need to answer one question fast: are these two cells the same colour, or opposite? Not what colour is this cell (you rarely know that), but how two cells are related, which you learn constantly.
That is a union-find with parity. An ordinary union-find stores, for each node, a parent pointer, and answers “same set?”. This one also stores a single bit per node saying whether it is the same as or opposite to its parent. Then:
- Every edge proven on merges its two faces as opposite.
- Every edge proven off merges them as same.
- The outer face is pinned OUT.
- A merge that contradicts a known relation is an immediate contradiction.
The bit is the whole idea. Walking to the root, you XOR the bits you pass, and that gives your parity relative to the root; two nodes with the same root are related by the XOR of their parities. The only subtlety is path compression: when you re-point a node straight at the root, its bit has to be rewritten to be relative to the root rather than to the parent you just skipped.
const find = (x: number) => {
let parity = 0;
let root = x;
while (parent[root] !== root) {
parity ^= rel[root];
root = parent[root];
}
// Re-point every node on the path at the root, rewriting each bit to be
// relative to the root rather than to the old parent.
let cur = x;
let curParity = parity;
while (parent[cur] !== cur) {
const next = parent[cur];
const nextParity = curParity ^ rel[cur];
parent[cur] = root;
rel[cur] = curParity;
cur = next;
curParity = nextParity;
}
return { root, parity };
};
const union = (a: number, b: number, parity: number) => {
const fa = find(a);
const fb = find(b);
if (fa.root === fb.root) return (fa.parity ^ fb.parity) === parity;
parent[fa.root] = fb.root;
rel[fa.root] = fa.parity ^ fb.parity ^ parity;
return true;
};union is where the whole scheme rests. Note what it buys: the
deductions propagate arbitrarily far. Two cells proven same-side across the
width of the board will, the moment anything makes them adjacent, force the edge
between them off. No chain of local rules would have found that.
The pattern rules are compiled lemmas
Every Slitherlink guide lists patterns. A 3 in a corner takes its two outer edges. Adjacent 3s force the edge between them and the two flanking edges. Diagonal 3s force their outer corners. A 0 beside a 3 decides most of the 3.
None of these are rules of the puzzle. Each is a two- or three-step theorem derivable from degree counting, clue counting and no-premature-closure, cached because a human (or a fast solver) would rather look one up than re-derive it.
That distinction matters for grading, which is the part guides do not care about and a generator must. A solver that hardcodes patterns gets speed and learns nothing about difficulty: it cannot tell you whether a board needs a pattern or merely admits one. A solver that implements the deep rules gets every pattern for free as a consequence, and can measure which ones a given board actually forces. If you want an honest difficulty stamp, implement the deep rules and let the patterns fall out.
What the ladder actually achieves
Four tiers, cheapest first, as in the other two puzzles.
I: local counting. Vertex degree and clue slack.
II: parity colouring. The union-find above, plus clue constraints re-read in colour terms: this 1 has three neighbours already known same-side, so the fourth must be opposite.
III: loop connectivity. No premature closure: track chains of on-edges with a second union-find over lattice vertices, and an edge joining two ends of the same chain would close a loop, which is only legal if it finishes the puzzle outright. Otherwise that edge is off. This is precisely Nurikabe’s “islands may not merge”. Plus chain reachability: a chain whose endpoints cannot reach the rest of the graph through undecided edges is a contradiction.
IV: search. Branch an undecided edge on and off, propagate, backtrack, and count solutions to two under a node budget.
Two things here are worth saying plainly rather than letting the tier list imply otherwise.
The first is that tier III never fires on a board this generator produces, even though it is perfectly reachable in principle.
Both halves of that are measured. On 3×3 there are few enough clue sets to enumerate the lot: of the 39,129 that are uniquely solvable, the ladder needs tier III on 1,832 of them. That is not rare. But on boards the generator actually ships (5×5, 6×6 and 7×7, twelve seeds at each difficulty) tier III decided nothing the parity colouring had not already decided. Zero out of thirty-six. So the stamp in practice reads I, II or IV.
The same enumeration turns up something I did not expect. Tier II is the rarest stamp on 3×3, not tier III: 160 boards against 1,832. The parity colouring is either not needed at all, because counting finishes the board, or it is not enough on its own. There is very little in between. I do not have an explanation I would defend; the tidiest guess is that a long-range rule either reaches across the board or does nothing local counting could not, but 3×3 is small enough that the effect may be an artefact of the size rather than anything about the rule.
That is not a bug, and I have left it. It is a finding about the generator rather than about the ladder: pushing for a target grade, it walks straight past the boards where loop connectivity is the deciding rule. Tier III still earns its place inside the uniqueness search, where its deductions prune branches even when they never decide a board on their own. Making III fire would mean implementing full dual-region connectivity (every cell of a colour class must stay reachable through undecided edges), which the current solver does not do. Worth building if the boards get bigger; not worth it for a 7×7.
The second is that tier IV is best-effort. The generator hill-climbs within a time budget and stamps what it achieved, so a board offered as “hard” is sometimes a strong tier II that the budget ran out on. The stamp is honest about what the solver needed; it is not a promise about what the generator was aiming for.
Generation runs backwards
The partition puzzles build a solution and read clues off it. Slitherlink does that too, but the second half inverts.
Draw a loop. Grow a random region cell by cell from a seed, rejecting any addition that creates a hole or a diagonal pinch, the same 2×2 test as above. Those two rejections are the whole of it: pass them and the region’s boundary is a single simple loop, with no separate check that it closed properly. Bias growth towards frontier cells far from the centroid and you get long, wandering loops instead of blobs.
Then delete clues. It is tempting to assume the fully clued grid is trivially unique: every cell’s count is determined by the loop, so what else could it be? It is not true, and it took an exhaustive search to convince me. On a 2×2 board the clues 2/3/3/2 admit two different loops; on 3×3, so do 1/2/3, 2/2/2, 3/2/1. Only three of 3×3’s 210 clue vectors are ambiguous, which is exactly why the assumption survives casual testing.
It also fails dangerously rather than loudly. An ambiguous starting board vetoes every deletion (each one is checked against a board that already has two solutions), so the generator rubs nothing out and ships the fully clued grid whole, stamped with one of its two answers and labelled unique. So the starting board gets checked like any other.
After that, shuffle the cells and, for each, tentatively remove its clue and re-run the uniqueness oracle; keep the removal if the puzzle is still unique. Deleting rather than adding is what makes this cheap: uniqueness is a property you are trying not to lose, so every check after the first is a veto rather than a search. This is Sudoku-style minimisation, and it is the difficulty dial. Greedy deletion to a fixpoint gives a locally minimal puzzle; the ladder grades it; hill-climbing over deletion order pushes towards a target. Sparse, pattern-breaking clue sets are exactly what force parity reasoning, because they are the ones where local counting runs out early.
This generator is far slower than the partition ones, because every candidate deletion costs a full solver run, which is why the node budget and an aggressive tier I/II pre-pass matter more here than anywhere else.
Slitherlink is NP-complete, shown by Takayuki Yato in 2000, and ASP-complete by Yato and Takahiro Seta in 2003. That second result is the one a generator lives with: holding a solution does not help you find another, so the uniqueness check inside that deletion loop has no shortcut in general. That is an asymptotic statement and a 7×7 board is a fixed size, so it proves nothing about this generator’s running time. What it does say is that no clever reformulation is waiting to be found, which is the practical content of a hardness result.
The three puzzles, side by side
| Cell Blocks | Nurikabe | Slitherlink | |
|---|---|---|---|
| State variable | rectangle per clue | cell owner | edge tri-state (+ face colour) |
| Candidate model | enumerated divisor rectangles | region growing | none; pure constraint state |
| Workhorse local rule | forced cell | island separators, 2×2 | vertex and clue counting |
| Mid-tier structure | orphan cells | reachability budgets | parity union-find |
| Global invariant | exact area cover | sea connected, no 2×2 | one cycle, IN simply connected |
| Search | MRV over candidates | cell sea / not-sea | edge on / off |
Every row changes. Cell Blocks enumerates candidate shapes and intersects them; Nurikabe cannot enumerate at all and grows regions instead; Slitherlink does not have candidates in any form, only booleans on edges. Three different answers to “what could this clue still be”, which was supposed to be the central question.
And yet the frame did not move once. Graded ladder, propagate to fixpoint, uniqueness by counting to two, node budget, generate against a difficulty target, stamp the deepest rung actually required. Written for rectangles, it survived region growing and then survived having no candidate model at all.
The one genuinely new thing across all three is the parity union-find. It has no analogue in the first two puzzles, its whole idea fits in a handful of lines, and it exists because Slitherlink is the only one of them with a topological invariant. Which, via the Jordan curve theorem, turned out to be a colouring problem all along.
Sources
- 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: ASP-completeness for Slither Link, Cross Sum and Number Place, the last of which you know as Sudoku. The Another Solution Problem itself is due to Nobuhisa Ueda and Tadaaki Nagao, “NP-completeness results for NONOGRAM via parsimonious reductions”, technical report TR96-0008, Tokyo Institute of Technology, 1996.
- The Jordan curve theorem.
- Nikoli’s own rules for Slitherlink.