Numberlink

The numbers have to balance before you draw anything

Colour the grid like a checkerboard. Any path alternates colours, so a path of m cells whose two ends are both dark holds one more dark cell than light; both light, one fewer; ends of different colours, exactly equal. In a solution the paths cover every cell, so adding those up over the whole board gives an identity that never mentions the paths at all:

#(pairs with both ends dark) − #(pairs with both ends light) = (dark cells) − (light cells)

The right-hand side is a property of h and w: zero when the area is even, one when it is odd. So on any board with an even number of cells the numbers whose two ends share the dark colour must be exactly as many as those sharing the light colour, and you can check that in a single pass over the clues — no search, no partial solution, nothing to back out of. Every one of the 99,636 partitions of the 4×4 grid satisfies it, and so does every partition of 2×3, 3×3, 3×4 and 3×5; the repository checks all of them on every test run.

Necessary, and not sufficient — the smallest witness is 2×3

Give a board exactly one pair of numbers and the puzzle collapses into a classical question: is there a Hamiltonian path between these two cells? Parity is the classical colour condition on that question, and it stops being sufficient almost immediately. On a 2×3 grid, put the two numbers on the middle cell of each row. They are 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 with one free neighbour cannot be an interior cell of anything. Across the placements this repository enumerates, 2×3 has one such position, 2×4 has two, 2×5 has three and 3×4 has seven — while 3×3, 3×5 and 4×4 have none at all, so the gap is not a function of size.

The rule Nikoli states as a matter of taste

Numberlink puzzles are conventionally drawn so that no path ever runs alongside itself: two cells of one path that touch on the grid are consecutive on that path. That reads like an aesthetic note. It is not. Sample random partitions of a 7×7 grid and number their ends: of 800 drawn without the constraint, 0 gave a board with a unique answer. Of 800 drawn with it, 72.8% did. On 9×9 it is 0 against 58.7%. Part of that is a confound and the repository measures it separately — taut paths are shorter, so a taut partition has more pairs, and more pairs is easier — but the effect survives holding the pair count fixed.

Four rungs, and one of them never fires

deg is the degree rule and nothing else: one line at a number, two everywhere else. It is where "every cell is used" actually lives, and on its own it settles about 8% of a 7×7 board. chain adds the shape rule — no closed loop, and no edge that would weld two different numbers together — and jumps to 77%. reach adds a connectivity test: both ends of a number must still be able to meet, and no region may be cut off with no number in it. probe tries each undecided segment both ways and keeps whichever survives.

reach is in the ladder because it seemed obviously useful and it is honest to report that it has never once changed an answer here. Over the 76 shipped boards it decides exactly as many segments as chain does, to the segment, and the search costs exactly the same number of branch points with it as without. That is a measurement, not a theorem — I do not have a proof that degree counting plus loop avoidance implies it.

Dropping "use every cell" — and finding it barely matters

The fill rule is what makes this a puzzle rather than a maze, so I expected removing it to blow the answer count up. It does not. Read the shipped boards as "just join the pairs, empty cells are fine" and 36 of the 40 7×7 boards still have exactly one routing; so do 31 of the 36 9×9 boards, and the median routing count is 1. The rule that defines the puzzle turns out to be almost redundant by the time these particular boards reach you.

That is a fact about the generator, not about Numberlink. Boards built from taut partitions are heavily over-determined — that is the same effect as the 0%-versus-72.8% above, seen from the other end. A board that only just manages to be unique under the full rules would fall apart without the fill rule; these do not, because they were never close to the edge.

What the ladder costs

Branch points needed to prove the answer unique, summed over all the shipped boards of a size:

* one 7×7 board and every 9×9 board hit a 300,000-branch cap, so the deg row is a lower bound. probe is 0 because singleton consistency finishes every shipped board without ever guessing.