Unlink

Every backtracking search has to undo things. The usual ways to afford that are a trail of changes, a stack of snapshots, or copying the state at each node — all of which cost memory that grows with depth. Knuth’s Dancing Links costs nothing, and the reason is four lines long.

The four writes

To remove node j from the vertical list it sits in:

j.D.U = j.U;
j.U.D = j.D;

Two writes, both to j’s neighbours. j.U and j.D are not touched. So the list no longer contains j, and j still points at exactly where it was. Putting it back is:

j.D.U = j;
j.U.D = j;

The removed node is the undo record. Nothing was saved anywhere, because nothing was lost. Knuth’s line for it is that the operations are “quadrilly reversible”; the demo’s version is that a removed node is drawn hollow with its two stale pointers still dashed in, pointing at neighbours that have stopped pointing back.

That is the only idea here. Algorithm X — pick an uncovered column, try each row in it, recurse — is three lines of ordinary backtracking on top.

Nothing above the links knows what it is solving

Four instances, one search:

The sudoku view draws a 9×9 grid, but the grid is a renderer. Nothing under it has heard of sudoku; it is covering columns. Modelling the problem is all of the work, and it is the part that never appears in the algorithm.

node scripts/measure.mjs runs all of them. Every line below is its output.

The matrix comes back

“Restored” is a checksum, not a claim. checksum() is FNV-1a over every L, R, U, D and size in the structure. Taken before the search and after it, those two values are compared, and the 6×10 enumeration — 1.2 billion unlinks, 1.2 billion relinks — comes back to 0x42302561 both times.

The solution counts are the arithmetic that says the model is right rather than merely consistent. Pentomino tilings are quoted in the literature up to each board’s symmetry, so the search should find exactly that many times the group size, and it does:

n-queens lands on 4, 92, 724, 2,680, 14,200 for n = 6, 8, 10, 11, 12. The twelve pentominoes come out to 63 orientations between them. A mistyped piece or an off-by-one in the constraint mapping would show up in all of those at once, which is the point of having them.

The search allocates nothing

The matrix is the only memory. There is no trail, no snapshot stack, no copy per node — so the footprint of a search is the footprint of the matrix, and the depth it reaches does not enter into it. Measured around the full 6×10 enumeration, with --expose-gc so the figure settles:

2,428,015,940 updates, 9,356 solutions, 20.7 s
heapUsed 27.60 MB -> 27.63 MB   (delta 0.03 MB)
nodes: 12,336 before, 12,336 after, 12,336 live

A consequence worth naming: the demo shows “live nodes” sixty times a second as nodeCount - (unlinks - relinks), one subtraction, because every unlink removes exactly one node and every relink restores exactly one. measure.mjs checks that cheap number against an O(nodes) walk of all four pointers of every node, 388 times mid-flight on a running search. Largest disagreement: zero. The structure never needed to be asked.

The high-water mark matters too. Across the 3×20 enumeration the most nodes ever spliced out at one time is a few thousand of 7,416 — so even if you did keep an undo log, it would be bounded by the matrix. The saving is not that the log is small. It is that the log is the thing itself.

Which column you pick is the entire algorithm

Algorithm X says “choose a column”. It does not say which, and that freedom is where all the performance lives. Same instance, same code, five rules, giving up after 200,000,000 updates:

Two things in that table. One: on sudoku the spread is past 100,000× and three rules never finish at all — they are not a slower version of the same search, they are a different search. Two: on n-queens, MRV is worth about 4×, and a rule that picks a column at random beats it.

Why 100,000× there and 4× here

The size of the column you choose is the branching factor at that node, so the thing to measure is that size, and the depth it gets compounded over:

Raise the ratio of the two branching factors to the depth and you have a prediction for the spread in the previous table. It is worth watching where that prediction breaks:

So the model holds on sudoku and queens and is flatly wrong on pentominoes. The honest reading is that MRV is two heuristics with one name:

• On sudoku it finds size-1 columns — 100% of choice points on the easy grids. A column with one row left is not a guess, it is a deduction, and the search takes it for free. Sixty levels of 1.00 against sixty levels of 1.38 is the whole difference between instant and never.
• On pentominoes it finds size-0 columns — 70% of choice points. Its chosen columns are larger on average than leftmost’s; it is not looking for narrow columns, it is looking for empty ones, and each one is a refutation reached without spending a guess on it. (The min chooser breaks out of its walk the instant it sees a zero, which is why finding one is cheaper than the walk.)
• On queens it finds plenty of both — more dead ends than sudoku has — and still only wins 4×, because the tree is eleven levels deep and eleven levels cannot compound a small per-node edge into a large one.

Clue count is not sudoku difficulty

A placement the search never takes back was forced. So “rows tried minus cells to fill” is exactly the amount of guessing in a whole solve:

The 17-clue grid is the sparsest a uniquely-solvable sudoku can be, and DLX solves it with no backtracking at all — 64 placements for 64 empty cells, every one of them forced. The 21-clue grid, with four more clues, takes 197 placements back. Clues constrain a puzzle; what makes it expensive is whether the constraint ever narrows to exactly one option, and those are not the same property. (The empty grid is also backtrack-free, for a different reason: with everything open, the first thing MRV tries always works.)

That also prices the part a human never does:

Where nothing was taken back, the proof is free — the tree was a single path and walking to the end of it is the search. Where there was guessing, proving uniqueness costs an order of magnitude more than finding the answer did.

Secondary columns, and the constraint exact cover cannot say

Exact cover means exactly once. N-queens needs at most once for diagonals, which is a different thing, and the way Knuth gets it is not a special case in the algorithm — it is a build-time decision about the header ring. A secondary column is created self-linked:

col.L = col.R = col;   // not spliced into the root's ring

It is in every row that touches it, so covering a row still unlinks through it and it still blocks a second queen. But it is unreachable from the root header, so no chooser can see it and h.R === h still means solved. The demo’s queens board is 20 primary columns and 38 secondary ones, and the search cannot tell the difference.

What is load-bearing and what is a drawing

• Verified against published values: every solution count above, the 63 pentomino orientations, the 12 distinct shapes up to rotation and reflection.
• Measured, not asserted: all the update counts, the checksums, the heap delta, the branching factors, the forced/dead fractions, the live-node identity.
• A modelling choice: the four sudoku grids, and the two labelled 21 and 23 clues are grids that circulate as hard for brute-force solvers — the description in this repo is just “hard”, because that is all that can be checked from here. The two-mechanism reading of MRV is an interpretation of the table above, not a theorem.
• A deliberate omission: no S-heuristic variants, no sparse-bitset DLX, no DLX2 with multiplicities. And the module uses object references rather than the integer arrays Knuth’s own implementation uses, which costs maybe 2–3× in throughput and buys a structure you can draw.
• An honest limit on “allocates nothing”: it is true of the search. The builders allocate — 12,336 node objects for the 6×10 board — and generator mode allocates an event object per yield, which is why solveFast exists.

Reuse

src/unlink.js is framework-free and has no DOM in it:

• buildMatrix({ columns, rows }) — columns take { name, primary }, rows take a list of column indices. That is the whole modelling interface.
• solveFast(m, { rule, limit, budget }) — counts, timings, solutions. Used for every number on this page.
• solve(m, { rule, fine }) — the same walk as a generator, yielding choose / try / untry / cover / uncover / unlink / relink / solution / dead. fine: true yields every individual node unlink, which is what makes the structure view steppable; fine: false drops those and runs about twenty times faster over the same search.
• checksum(m), liveNodes(m), liveNodesFast(m), activeNodes(m) — the measuring instruments, and isLive(n) / isCovered(c), which the demo uses to decide how to draw a node rather than tracking a flag of its own.
• verifyPaths(build, opts) — runs both code paths over fresh matrices and asserts they agree on solutions, updates, rows tried and depth. Two implementations of one algorithm is a real risk; this is what holds them together, and measure.mjs runs it on six instances.

src/problems.js carries the four instances and nothing else. Adding a fifth is a function returning { columns, rows }.

The demo is demo/index.html with its own copy of both modules (ADR-0002) and a window.__demo hook the screenshot rig drives. node scripts/screenshot-demo.mjs regenerates the thumb and all seven media shots and doubles as the smoke test: it drives a real search in a real browser and asserts the live-node identity and the restoration checksum on the way out.