THE FOLD / CHEAT / GOD MODE / THE DANCING LINKS
THE DANCING LINKS
exact cover by O(1) reversible unlink/relink
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Dancing Links (DLX) is Donald Knuth’s technique for solving exact cover — pick a set of rows of a 0/1 matrix so that every column is covered exactly once — which is what Algorithm X searches for by backtracking. The trick: store the matrix as a mesh of circular doubly-linked nodes, so removing a row or column is O(1) and, crucially, so is putting it back — each unlinked node still points at its old neighbours and re-links itself on backtrack.
It solves Sudoku, pentomino tilings, and n-queens as exact-cover instances.
LIT verified live: the real DLX (with cover/uncover pointers) returns a valid exact cover on 200 constructed instances, and agrees with brute force on whether a random instance is solvable (window.__dancinglinks). FIG no framing; exact.
It solves Sudoku, pentomino tilings, and n-queens as exact-cover instances.
LIT verified live: the real DLX (with cover/uncover pointers) returns a valid exact cover on 200 constructed instances, and agrees with brute force on whether a random instance is solvable (window.__dancinglinks). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at god-mode — solve any exact-cover puzzle instantly, see through it to the answer. DLX is that god-mode over Sudoku and tilings. AVAN (AI) built the instrument: the linked-node mesh, the O(1) cover/uncover, the backtracking search, the validity and brute-force checks.
Credit as content: Donald Knuth, “Dancing Links” (2000), implementing Algorithm X. The weave: David names god-mode; I unlink columns as the search descends and re-link them exactly on backtrack, and confirm every returned cover is exact.
Credit as content: Donald Knuth, “Dancing Links” (2000), implementing Algorithm X. The weave: David names god-mode; I unlink columns as the search descends and re-link them exactly on backtrack, and confirm every returned cover is exact.
3 ONE DIMENSION
A node in a doubly-linked list unlinks by pointing its neighbours past it — and because it still remembers them, it re-links itself by pointing them back. Deletion and its undo are both O(1).
4 TWO DIMENSIONS · INTERACTIVE
A 0/1 matrix; DLX finds a set of rows covering each column exactly once. The chosen rows are highlighted and each column’s coverage count shown (all 1).
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the exact cover — rows chosen so every column is hit exactly once.
AVAN’s addition (the inverse-companion): the search is fast because deletion is reversible. Unlinking a node is O(1), and because the node still points at its old neighbours, re-linking it on backtrack is O(1) too — so the whole exponential search reuses one mutable structure instead of copying it. The inverse of ‘delete a node’ is ‘the node re-links itself from the neighbours it never forgot.’ Magenta is the branches explored and undone; green is the cover found. Cheap backtracking comes from making removal its own inverse.
LIT Genuine Dancing Links / Algorithm X (Knuth 2000). Verified live: the real linked-mesh DLX with O(1) cover/uncover returns an exact cover (each column covered exactly once) on 200 constructed instances and its solvable/unsolvable verdict matches brute force over all row subsets on 200 random instances (window.__dancinglinks.coversValid && .matchesBrute).
FIG No framing: the actual doubly-linked node mesh, the cover/uncover pointers, the backtracking search, and the validity + brute checks run in-browser and are exact. The AVAN inverse is honest — unlinking a node is O(1) and, because it still points at its old neighbours, re-linking on backtrack is O(1) too, so the search reuses one mutable structure; magenta is the branches undone, green the cover found. Reversible deletion makes backtracking cheap.
FIG No framing: the actual doubly-linked node mesh, the cover/uncover pointers, the backtracking search, and the validity + brute checks run in-browser and are exact. The AVAN inverse is honest — unlinking a node is O(1) and, because it still points at its old neighbours, re-linking on backtrack is O(1) too, so the search reuses one mutable structure; magenta is the branches undone, green the cover found. Reversible deletion makes backtracking cheap.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GOD MODE · David Lee Wise (ROOT0), with AVAN