SEN LLC

Posted on Aug 27

Numbrix: one number colours the whole board, and the ruler rung that provably pays nothing

#typescript #algorithms #gamedev #puzzle

Numbrix in the browser with five rule sets inside. Fill the grid
with 1 … n so that consecutive numbers share an edge. Strip the
labels and the answer is a Hamiltonian path of the grid graph — the
numbers only record the order you walked it in. Puzzle #47 in the solver
series.

Demo: https://sen.ltd/portfolio/numbrix/
Repo: https://github.com/sen-ltd/numbrix

One number colours the whole board

Colour the grid like a chessboard. The walk changes colour at every step, so
the colour of the cell holding v is the colour of the cell holding 1,
flipped v−1 times: value parity and cell colour are locked together,
globally. Print a single number anywhere and every other number on the board
learns which half of the grid it lives in.

This is the cheapest and widest clue this series has measured. On random 8×8
answers, counting surviving cell×number pairs:

board	numbers printed	after `pin`	after `link`	cells pinned
8×8	0	100.0%	100.0%	0.0%
8×8	1	96.9%	43.0%	1.6%
8×8	2	93.9%	36.9%	3.3%
8×8	4	88.0%	27.7%	6.8%
8×8	8	76.8%	13.5%	17.5%
10×10	1	98.0%	44.4%	1.0%
10×10	8	84.7%	19.5%	9.8%

Plain bookkeeping (pin) removes one printed number from 63 other cells and
stops. Turning the same clue into a global statement is the chain rule's
doing. And the first clue takes more than half; every clue after it is
suddenly cheap — the chessboard is only bought once.

The solver hard-codes none of this. The value chain 1—2—…—n is a
tree-shaped constraint network, arc consistency on a tree is exact, and the
chessboard falls out as a consequence rather than a rule.

Two corollaries, both checked on 1,400 sampled answers:

value parity ≡ cell colour (1,400 / 1,400)
an odd cell count puts both ends of the walk on the same colour, an even one puts them on opposite colours (600 odd boards and 800 even boards, no exceptions)

The ruler rung that pays nothing

For a puzzle about consecutive numbers, everybody's second rule is a ruler.
Walking from u to v takes exactly |v−u| steps and no walk beats the grid
distance, so a cell far from every home of u loses a whole interval of
numbers around u. It is sound, it is cheap, and it is the technique
humans actually use.

It is also provably worthless after link. The value chain is a path, arc
consistency on it is exact, so every candidate link leaves standing takes
part in some complete walk — and that walk is itself the witness for the
distance bound. Anything you can prove with a ruler, the chain has already
proved.

To keep the claim measurable rather than rhetorical, ruleSpan still ships,
unused by the ladder. On 160 random boards:

board	boards	bits after `pin` alone	pinned by pin+ruler	pinned by pin+link
4×4	40	2,851	55.8%	57.3%
6×6	40	20,904	63.3%	64.9%
8×8	40	75,417	56.4%	57.8%
10×10	40	196,219	59.4%	61.2%

Not a weak rule — a redundant one. On its own it does very nearly the chain's
job (1.4–1.8 points less reach). After the chain it deletes nothing at all.

What survives the argument is distinctness

The relaxation the chain solves exactly is a walk: it may step on its own
tail. Everything the real puzzle knows beyond that says the walk is a path —
that it uses distinct cells. There are two ways to say it.

block, the pigeonhole. The values a…b need b−a+1 distinct cells, all from the union of their surviving homes. A smaller union kills the board; a union of exactly that size is a tight set whose cells belong to the block and lose everything else. Read from the cells instead of the values ("if b−a+1 cells have nothing left but a…b, every other cell loses a…b") it prunes the other direction. Both halves of Hall's condition.
edge, the degree count. Forget numbers; look at the drawing. Every cell has path-degree 2 except the two ends. A cell with exactly two possible edges must use both; forced edges glue into runs whose labels are consecutive by construction; a run may never close a cycle; and what survives must keep the board connected.

Stacking rungs from the bottom (cells pinned, random reveals):

board	reveal	`pin`	`link`	`block`	`edge`	`probe`
8×8	20%	20.9%	43.3%	47.5%	53.5%	74.7%
8×8	30%	30.7%	71.9%	74.5%	84.6%	88.8%
8×8	40%	40.6%	86.6%	87.4%	94.1%	96.9%
10×10	20%	21.0%	47.0%	50.7%	61.5%	77.8%
10×10	30%	31.5%	78.8%	80.2%	88.6%	93.4%
10×10	40%	41.4%	90.6%	91.3%	97.3%	97.9%

One load-bearing rung, three accelerators

That table adds rungs from the bottom. Deleting one from the top says
something different, and you need both to avoid lying to yourself:

10×10, variant	cells pinned	boards whose fixpoint moved	pin scans	link scans	edge runs	probes
full	84.9%	—	496,439	471,796	4,484	1,763
−pin	84.9%	0 / 12	0	556,574	5,250	1,763
−link	37.3%	12 / 12	26,300	0	263	72
−block	84.9%	1 / 12	714,182	687,840	6,726	2,015
−edge	84.9%	1 / 12	703,965	660,469	0	2,520
−probe	74.3%	9 / 12	11,300	11,300	113	0

Only link carries reach. Everything else is speed. Dropping the degree
count leaves the same cells pinned on 11 of 12 boards — while raising the
bookkeeping bill by 42% and the probe count by 43%, because the probe
has to re-derive by contradiction what the drawing said for free. What edge
looked like it was earning in the incremental table was really "work the
probe didn't have to do".

Ink, spent well and spent badly

A Numbrix clue set is small — but only if the setter picks it. The left
column is the irredundant set an adversary finds (reveal until the level
finishes, then take back every number it can do without); the right is what
the same board needs when numbers are revealed in random order until the
answer becomes unique.

board	adversarial, `edge` level	as % of cells	random reveal until unique (median)	ratio
4×4	3	18.8%	31%	1.7×
6×6	6	16.7%	22%	1.3×
8×8	10	15.6%	30%	1.9×
10×10	15	15.0%	49%	3.3×

The adversarial share falls as the board grows — 15% of a 10×10 is enough —
while random ink wants half the board. Give the probe the same job and 10×10
drops to 12 numbers.

At the bottom of the ladder there is a wall rather than a curve. With only the
bijection to reason from, a cell becomes pinned exactly when it is printed or
when it is the last unclaimed one, so pin cannot finish any board that is
not already printed in full. Measured: 15 of 16 numbers on a 4×4 and
35 of 36 on a 6×6, every single time. The bank has no pin grade because
no such puzzle exists.

Reading a second answer off the answer

A Numbrix answer is a walk, so the cheapest way to build a different answer
out of one you have is the classic 2-opt reversal: pick two positions on
the path whose cells happen to be grid neighbours, and walk the stretch
between them backwards. It needs one extra edge at each end of the window and
no printed number inside it. Scanning every pair is O(n²) with O(1) work
each — a second answer read straight off the first, with no search.

board	ambiguous boards	explained by one reversal	false alarms on unique boards
4×4	60	83.3%	0 of 35
6×6	60	70.0%	0 of 24
8×8	60	63.3%	0 of 3
10×10	60	58.3%	—

The false-alarm column thins out on the big boards because that stream was
deliberately under-clued to produce ambiguity — so the shipped bank does the
same job at full strength: all 64 boards are unique and not one carries
a certificate. That the explained share falls with board size is the honest
reading: on a big grid a second answer can be a re-route the walk never comes
back from.

The move below a reversal does not exist. A single cell can never change its
number quietly — it would appear twice and another would vanish — and the
tests check that exhaustively over every cell and every alternative on 4×4.

Sampling an answer without ever searching for one

A rectangle always has a Hamiltonian path — the boustrophedon one, snaking row
by row — so a Numbrix answer can never fail to exist. The problem is the
opposite: that answer is far too regular to print, and rejection-sampling
random walks until one covers the board is hopeless past 5×5.

So the generator moves between answers instead of drawing one. The
backbite move takes a Hamiltonian path, picks one of its two ends, picks a
random grid neighbour u of that end, and — if u is not already the next
cell along — adds the edge (end, u) and deletes the edge that used to enter
u from the far side. The result is another Hamiltonian path of the same
grid. Always. No rejection, no restart, no failure mode.

board	moves per cell	accepted	turns in the answer	distinct answers in 200 draws
10×10	0 (the snake)	—	18.0	1
10×10	1	69.8%	33.1	200
10×10	4	71.7%	50.9	200
10×10	16	71.8%	55.9	200
10×10	60 (shipped)	72.0%	55.4	200

The snake has 2(n−1) = 18 turns and exactly one form. Sixteen moves per cell
triples the turn count and the sampler has stopped moving — 200 draws, 200
different answers, about seven moves in ten accepted at every size.

The external ledger

The raw engine shares no candidate machinery with the ladder: it walks, and
scores completed walks with the rule text. Switch the printed numbers off and
it becomes a census machine — and these are published combinatorics, not
something this repository can quietly agree with itself about.

board	directed Hamiltonian paths, engine	published
3×3	40	40 — OEIS A096969
4×4	552	552
5×5	8,648	8,648
6×6	458,696	458,696

board	Hamiltonian cycles, engine	published / proved
4×4	6	6 — OEIS A003763
6×6	1,072	1,072
3×3, 5×5	0	0 — theorem: a cycle alternates colours, an odd cell count cannot

And one identity proved rather than looked up. On the 2×m ladder a walk can
only leave a column through its own rung, so it sweeps the columns
monotonically from each end and is fixed by its turning column — giving
m² − m + 2 undirected Hamiltonian paths. The engine, which knows nothing
about ladders, produced 4, 8, 14, 22, 32, 44, 58 for m = 2…8. Exactly.

probe ⇔ unique

The two engines agreed on every solution count they both finished. And
probe-completion ⇔ uniqueness held on 160 boards in both directions with
zero disagreements:

board	boards	probe finishes & unique	probe stalls & ambiguous
4×4	40	21	19
6×6	40	16	24
8×8	40	7	33
10×10	40	6	34

Every one of the 64 shipped boards was re-proved unique by both engines before
shipping.

Takeaways

One printed number colours the whole board. Surviving cell×number pairs on an 8×8 go 100% → 43.0% with one clue; a second only reaches 36.9%. The chessboard is bought once. The solver hard-codes none of it — arc consistency on the path-shaped value chain rediscovers it
Corollaries, no exceptions on 1,400 answers: value parity ≡ cell colour, and an odd cell count puts both ends of the walk on the same colour
The ruler rung deletes 0 bits after link (160 boards). Not weak — redundant: on its own it deletes 2,851–196,219 bits and comes within 1.4–1.8 points of the chain's reach. Anything a distance argument can prove, an exact arc consistency on a tree has already proved
What survives the argument is distinctness: block (both halves of Hall's condition) and edge (degree and connectivity) are the two ways to say the walk is a path
The incremental table and the ablation table disagree, and both are true: only link carries reach (84.9% → 37.3% without it), while dropping edge leaves 11 of 12 fixpoints bit-identical and raises the bookkeeping bill 42% and the probe count 43%
Adversarial ink: 15 numbers on a 10×10 (15%) against 49% revealed at random — 3.3×. pin provably needs n−1, so no pin-grade puzzle exists
The 2-opt reversal certificate explains 58–83% of ambiguous boards with no search and 0 false alarms; a single cell can never change alone
Generation is backbite — moving between answers, never searching for one. 16 moves per cell gives 200 distinct answers in 200 draws
External ledger: 40 / 552 / 8,648 / 458,696 directed Hamiltonian paths (A096969), 6 / 1,072 cycles (A003763), 0 on odd boards (theorem), and a self-proved m² − m + 2 for the 2×m ladder, every term

33 tests. TypeScript, zero runtime dependencies.