Numberlink in the browser with a four-rung solver. What I look for in
this series is something you can read off the board without solving it. This
time it turned up in the clue placement itself: checkerboard-colour the grid
and one pass over the numbers tells you whether the board can have an answer
at all. Puzzle #54 in the solver series.
Demo: https://sen.ltd/portfolio/numberlink/
Repo: https://github.com/sen-ltd/numberlink
Rules
- Join each pair of equal numbers with a path of orthogonally adjacent cells.
- No two paths share a cell, and no path crosses itself.
- Every cell of the grid is used.
Rule 3 is Nikoli's, and a lot of connect-the-dots games drop it. There is also a
convention that no path ever runs alongside itself — two cells of one path
that touch on the grid are consecutive on that path. That one is normally
presented as a matter of taste. I measured it. It is not a matter of taste.
The identity that only mentions the clues
Colour the grid like a checkerboard: cell (r, c) is dark when r + c is even.
A path steps one cell at a time, so it alternates colours. For a path of m
cells:
| the path's two ends | length | dark − light |
|---|---|---|
| both dark | odd | +1 |
| both light | odd | −1 |
| different colours | even | 0 |
In a solution the paths cover every cell of the grid. So summing those ±1s
over all the paths has to give the board's own imbalance — and what is left is
an equation that never mentions a path:
#(pairs with both ends dark) − #(pairs with both ends light) =
(dark cells) − (light cells)
The right-hand side is fixed by h and w alone: 0 when the area is even,
1 when it is odd. So:
On any even-area board, the numbers whose two ends share the dark colour must
be exactly as many as those sharing the light colour.
You check that in one pass over the clues. No search, no partial solution,
nothing to back out of. The implementation is about twenty lines (parityOf in
src/numberlink.ts), and the demo page runs the tally live in a panel next to
the board.
The test suite verifies the identity against every partition of the 3×4 and
4×4 grids — 102,749 of them, zero violations — on every run. npm run stats
extends it to 2×3, 3×3 and 3×5 for 137,789 in total.
Necessary, and not sufficient. The witness is 2×3
. 1 .
. 1 .
The two 1s are on cells of different colours, so the count balances. There is
still no answer. Whichever way you leave the top middle cell you strand a
corner, and a corner has only two neighbours, so it cannot be an interior cell
of any path — interior cells need degree two and a stranded corner is a dead
end.
Give a board exactly one pair and the puzzle collapses into a classical
question:
Is there a Hamiltonian path between these two cells?
One path using every cell is a Hamiltonian path, and the colour count above is
exactly the classical colour condition on grid graphs. Enumerating every
single-pair placement:
| board | balance, solvable | balance, no answer |
|---|---|---|
| 2×2 | 4 | 0 |
| 2×3 | 8 | 1 |
| 2×4 | 14 | 2 |
| 2×5 | 22 | 3 |
| 3×3 | 10 | 0 |
| 3×4 | 29 | 7 |
| 3×5 | 28 | 0 |
| 4×4 | 64 | 0 |
The interesting part is that it is not monotone. 2×3 has a witness and 3×3
has none; 3×4 has seven and both 3×5 and 4×4 have none. The gap is a function of
the board's shape, not its size.
The convention turns out to be nearly all of the uniqueness
Generation in this series runs backwards: cut the grid into paths first, then
write a number on each path's two ends. Every board produced that way
already has an answer by construction — the only question is whether it has
more than one.
So I sampled partitions and measured how often the board is unique:
| board | partitions sampled | drawn without the convention | with it |
|---|---|---|---|
| 7×7 | 800 each | 0.0% unique | 72.8% unique |
| 9×9 | 300 each | 0.0% unique | 58.7% unique |
Zero out of 800, against 583 out of 800.
There is a confound, and it is worth naming rather than hiding: taut paths grow
less far, so they are shorter, so a taut partition leaves more pairs — and
boards with more pairs are easier to pin down. So I bucketed by pair count and
compared inside each bucket:
| pairs | loose | taut |
|---|---|---|
| 5 | 0.1% of 1274 | 40.0% of 55 |
| 6 | 0.0% of 1079 | 54.8% of 301 |
| 7 | 0.4% of 571 | 72.4% of 909 |
| 8 | 0.9% of 229 | 85.3% of 1153 |
| 9 | 1.3% of 77 | 89.9% of 936 |
The effect survives intact. This is also the only reason a 9×9 bank exists in
this repository at all: before the sampler enforced tautness, four thousand
draws produced zero unique boards.
Four rungs, and one of them never fires
The solver does not think in paths. It assigns ON / OFF / undecided to the
h(w−1) + (h−1)w segments between cells, which splits the puzzle into two
constraints that look nothing alike:
- degree — a numbered cell has exactly one ON segment, every other cell exactly two.
- shape — the ON subgraph is a forest of paths, and each path's two ends carry the same number.
Rule 3 — "every cell is used" — disappears entirely into the degree line. A cell
with degree two is on somebody's path by construction. Collapsing the rule that
defines the puzzle into one clause was the nicest part of the build.
The rungs:
-
deg— degree counting only. -
chain— union-find over the ON components; turn off any segment that would close a loop or weld two different numbers onto one path. -
reach— connectivity: both ends of every number must still be able to meet, and no region may be sealed off with no complete pair inside it. -
probe— try each undecided segment both ways, keep whichever survives.
Decided from a blank slate:
| board | deg |
chain |
reach |
probe |
|---|---|---|---|---|
| 7×7 | 8.4% | 76.7% | 76.7% | 100% |
| 9×9 | 4.5% | 53.6% | 53.6% | 100% |
Branch points to prove uniqueness, summed over the bank:
| board | deg |
chain |
reach |
probe |
|---|---|---|---|---|
| 7×7, 40 boards | 3,306,784 * | 172 | 172 | 0 |
| 9×9, 36 boards | 10,800,036 * | 2,827 | 2,827 | 0 |
* one 7×7 board and all 36 9×9 boards hit a 300,000-branch cap, so the deg
row is a lower bound.
Look at the reach column. It is identical to chain — same decided
fraction, same branch count, digit for digit. Across 2,488 comparisons
(blank slates, partly-drawn boards, shipped boards, random boards) reach has
never once reached a different conclusion than chain.
I added reach because it looked obviously useful. It is not. I have no proof
that degree counting plus loop avoidance implies connectivity here, so this goes
in as a measurement rather than a theorem — and the rung stays in the ladder and
in the demo's dropdown, because a rung that never fires is part of the result.
Dropping "every cell is used" changes almost nothing
Rule 3 is what makes Numberlink a puzzle rather than a maze, so removing it
ought to blow the answer count up. It does not:
| board | still unique without rule 3 | median routings |
|---|---|---|
| 7×7 | 36 / 40 | 1 |
| 9×9 | 31 / 36 | 1 |
Nine boards in ten are already unique when read as "just join the pairs, empty
cells are fine". The rule that defines the puzzle is nearly redundant by the
time these particular boards reach you.
That is a fact about the generator, not about Numberlink. Boards grown from taut
partitions are heavily over-determined; they are nowhere near the edge of
uniqueness. It is the 0%-versus-72.8% result seen from the other side. A board
that only just manages to be unique under the full rules would fall apart the
moment you dropped rule 3.
Generation: answer first, then repair
Cutting the grid into taut paths first means an illegal board is unreachable —
"every cell is used" is precisely what a partition is. No rule ever needs
checking afterwards. Only uniqueness needs a search.
And Numberlink has no "add a hint" move. The clues are the path ends, so
adding a number means changing the shape of the answer. When a board comes out
ambiguous the generator therefore does not resample. It repairs:
- take two answers;
- list the cells where they disagree;
- cut the path running through one of them in two — which adds exactly one pair;
- repeat until unique.
Aiming the cut at the disagreement kills the intruder without scattering extra
numbers across the board.
Counting the grids themselves
Forget the numbers: how many ways does an h × w grid fall apart into paths of
two or more cells?
2xn: 1, 6, 26, 118, 528, 2364, 10580, 47352, 211928, 948504, 4245120, 18999440
3xn: 1, 26, 242, 3113, 34772, 412016, 4758383
4xn: 2, 118, 3113, 99636, 2993923
None of the three is in OEIS (searched 2026-09-04). The 2×n row satisfies
a(n) = 5a(n−1) − 2a(n−2) − 2a(n−3) + 2a(n−4)
for every term computed. It was fitted on four terms, so four of the eight
checks are genuine predictions — but there is no proof here, only the fit.
The bug that inverted a conclusion
The scariest bug in the build was in the routine that counts routings with rule
3 switched off. It pulled its four-element neighbour buffer from a pool indexed
by path length:
const b = buf[path.length]; // ← here
const m = neighbors(g, cur, b);
for (let i = 0; i < m; i++) { ... }
When one pair finishes, the next pair restarts at length 1 — and overwrites
buf[1] while an ancestor frame (the first pair, back when it was at length 1)
is still iterating over it. Routings get skipped.
Measured with that bug in place, the first numbers said 6 of 40 boards were
unique without rule 3, with a median of 14.5 routings. That is the exact
opposite of the section above: it said the fill rule was carrying the
uniqueness. A whole section of this article was written backwards and had to be
thrown away.
No puzzle-level test catches this. Does the board solve? Yes. Is the answer
unique? Yes. What caught it was the most boring assertion in the suite, the one
I nearly did not bother writing:
it('is at least as generous as the full puzzle', () => {
// every answer with the fill rule is also an answer without it
expect(without).toBeGreaterThanOrEqual(withFill);
});
Removing a constraint reduced the number of solutions. Allocating a fresh
four-element array per frame fixed it.
Two engines
Everything above is cross-checked by two solvers that share no code. One assigns
ON/OFF to segments and propagates degrees and connectivity. The other never
mentions a segment: it cuts the grid into paths directly, anchoring on the
lowest free cell, and keeps the cuts whose pieces happen to be numbered
correctly. They agree on the answer count for 400 random boards on 3×3 through
4×4, and on which parity-impossible placements have no answer at all.
Takeaways
- The checkerboard argument gives an identity that closes on the clue placement alone — board feasibility without any search.
- Necessary, not sufficient; the witness is 2×3, and a one-pair board is exactly a Hamiltonian path problem.
- The "no path runs alongside itself" convention decides almost all of the uniqueness — 0% against 72.8%, and it survives fixing the pair count.
- The connectivity rung never fired in 2,488 comparisons. No proof, so it ships as a measurement.
- "Every cell is used" is nearly redundant on these boards — which says more about the generator than about the puzzle.
- 74 tests, and the boring inequality test is the one that earned its keep.
Demo: https://sen.ltd/portfolio/numberlink/
Repo: https://github.com/sen-ltd/numberlink
Top comments (0)