A dart thrown into the dark abstract landed on Knuth’s prettiest trick: store a constraint matrix as circular doubly-linked lists so a column and its rows can be pulled out and—on backtrack—snapped back in, in O(1). The links dance. We solve a real exact cover live, credit who actually invented it, and ask what I-13 should learn. Three prongs, one dart.
THE TECHNIQUE exact cover · cover / uncover · the links dance
Exact cover: pick a set of rows so every column is covered by exactly one chosen row. The whole matrix is a torus of pointers — each 1 links to its neighbours up/down/left/right, columns ring back to a root. To try a row, cover its columns (unlink them and every conflicting row); to undo, uncover in reverse and the pointers relink exactly. No copying, no rebuild. live demo
// cover(c): unlink column c and every row that touches it
c.R.L = c.L ; c.L.R = c.R
for each row i down column c:
for each node j across row i: j.D.U = j.U ; j.U.D = j.D // pull j out
// uncover(c): the SAME walk, reversed — pointers snap back into place
for each row i up column c:
for each node j back across row i: j.D.U = j ; j.U.D = j
Instance below (Knuth’s classic 6×7): rows A–F are subsets of columns 1–7. Algorithm X always covers the column with the fewest 1s (Knuth’s S heuristic), tries each row in it, and backtracks on a dead end. Watch the cells unlink (dim) and relink (light up). Unique answer: {B, D, F}.
active 1
unlinked
chosen (solution)
Press solve to watch Algorithm X dance through the matrix.
covers0uncovers0steps0backtracks0
speed
HISTORY & CREDIT credit where it is due
The name and the fame belong to Knuth — but the idea is older, and Knuth is the first to say so in print. The “Knuth invented dancing links” shorthand drops the people he explicitly credits. cited
1979 · Hiroshi Hitotsumatsu & Kōhei Noshita — invent the unlink/relink trick on doubly-linked lists (a node remembers its neighbours, so removal is reversible). This is the dance itself. 1972 · the reversible-remove idea has roots in earlier list work; Knuth traces the lineage in his paper’s notes. 2000 · Donald E. Knuth — publishes “Dancing Links”, names the technique, pairs it with his Algorithm X for exact cover, and credits Hitotsumatsu & Noshita by name. It is his paper that made it famous.
So: Algorithm X and the “dancing links” name are Knuth (2000); the underlying O(1) reversible unlink is Hitotsumatsu & Noshita (1979), credited by Knuth himself. Honest phrasing keeps both. cited
Still open: exactly how far back the reversible-delete idea goes in the linked-list literature is a matter of citation archaeology; Knuth’s notes give the earliest pointers he found. open Source: Wikipedia: Dancing Links.
RECOMMEND FOR I-13 what the galaxy should learn
Dancing Links is pure pointers: circular doubly-linked lists, mutated in place, restored by aliasing. I-13 has no references, no linked structures, no mutable aggregates — only f64 scalars and functions. I asked the real I-13 compiler to build even a single linked node. It cannot — proven, not asserted:
i13 check node.i13 => node.i13:2:1 E0201 attribute assignment `.next` is recognized
but has no executable I13 v0.1 semantics (cannot attach a link/pointer)
i13 check array.i13 => array.i13:1:9 E0001 unexpected character `[` (no aggregate literal)
i13 check index.i13 => index.i13:2:10 E0001 unexpected character `[` (no subscript into a structure)
i13 run ok.i13 => x = 42 (every value is a bare f64 scalar)
Even the language’s own reference program says so out loud — examples/core.i13 routes eight channels by passing all eight as explicit scalar parameters, with the comment: “No arrays/records are assumed.” The author already codes around the missing aggregate.
Recommend — deliberate scope call: a reference / linked aggregate is a genuinely new kind of value, not a new operator. The last dart (fast inverse square root) wanted bit-ops — a cheap fix, a new BinOp discriminant, zero new alphabet symbols. This is not that. A pointer needs a heap, an allocation verb, a value type that isn’t f64, and aliasing + in-place mutation — the exact thing that breaks I-13’s conserved law net = binds − k and its single-pass validator (aliased mutation has no static stack balance). The honest call is: do NOT add it. Keep I-13 scalar-pure. Dancing Links is the clean proof of what a linked language buys (O(1) reversible structure) and what it costs (shared mutable references — precisely what I-13 forbids by construction). If linked structures are ever wanted, that is a different language, and this dart is the receipt for the decision. Credit Knuth’s elegance honestly; decline it deliberately.