Every one of this site's other nine Backtracking entries shares the same undo: push a value onto an array, or fill a grid cell, then pop it or clear it back out the moment a branch fails. This entry keeps the reject/place/backtrack shape but changes what "undo" means. It's built for a specific reformulation called exact cover: given a universe of items and a collection of candidate subsets, choose a subcollection whose union is the whole universe and which never overlaps — every item covered by exactly one chosen subset, no item left out, no item covered twice. Sudoku and N-Queens are both, underneath, exact cover problems in disguise (see Complexity below). Algorithm X is Knuth's name for the search; Dancing Links is the data structure that makes each undo an O(1) pointer restore instead of a rescan — cover a column by unlinking it from a circular doubly linked list, and undo it later by relinking the exact same pointers in the exact reverse order, which Knuth described as looking like a well-choreographed dance.
The matrix below is Knuth's own toy example from the 2000 paper that introduced this technique: 7 items (columns 1–7) and 6 candidate rows A–F, where A = {1,4,7}, B = {1,4}, C = {4,5,7}, D = {3,5,6}, E = {2,3,6,7}, F = {2,7}. Algorithm X repeatedly picks a still-uncovered column and tries every candidate row that has a 1 there. Selecting a row covers that column and every other column the row touches — which "dances out" every other row sharing any of those columns, since a row with no columns left to offer can never be part of a valid cover. If every column ends up covered, that's a solution. If a chosen column ever has zero live candidate rows, that branch is dead: dance everything the last selection removed back in, in the exact reverse order, and try the next row. Switch the column-choice rule below to compare Knuth's own heuristic — always cover whichever column currently has the fewest live candidates — against always covering the leftmost remaining column instead; both reach the identical solution, only the cost differs (see Pitfalls).
Every column has a header node holding a live size count and vertical
U/D pointers threading a circular list through every row-node that has a 1
in that column. Every row threads its own nodes together horizontally with L/R
pointers, circularly. A master header links every still-uncovered column left-to-right.
cover(column) does two things: unlink the column header itself from the
master row (O(1)), then walk every row-node in the column's vertical list and, for every other
node in that row, unlink it from its own column's vertical list and decrement that column's size. Read
that carefully: nothing is deleted, no array is copied — every node keeps its old pointers, it's just
no longer reachable by walking from a live header. uncover(column) is the
exact mirror, walking the same nodes in the exact opposite order and relinking them, which is why this
still works even though nothing was ever actually removed: the stashed pointers are still sitting
there, unchanged, ready to be pointed back to.
Verified three ways before writing any of the numbers below. First, the Knuth example: exhaustively
checked all 26 = 64 subsets of the 6 candidate rows by brute force, found
exactly one exact cover — {B, D, F}, since {1,4} ∪ {3,5,6} ∪ {2,7} is exactly {1,...,7} with no
overlap — and confirmed the dancing-links search finds that identical, unique answer. Second, a
3,000-trial stress test against the same brute-force checker on random small instances (4–7 columns,
3–10 rows each): 0 mismatches, every instance's full solution set matched exactly, including instances
with zero, one, and many solutions. Third, the column-choice comparison in Pitfalls below was measured
directly from the same reference implementation shipped on this page, not estimated.
function solveExactCover(columnsCount, rows) {
const header = {}; header.L = header; header.R = header;
const cols = [];
for (let c = 0; c < columnsCount; c++) {
const col = { size: 0 };
col.U = col; col.D = col;
col.L = header.L; col.R = header;
header.L.R = col; header.L = col;
cols.push(col);
}
rows.forEach((rowCols, rIdx) => {
let first = null, prev = null;
rowCols.forEach((c) => {
const col = cols[c];
const node = { row: rIdx, col };
node.U = col.U; node.D = col;
col.U.D = node; col.U = node;
col.size++;
if (!first) { first = node; node.L = node; node.R = node; }
else { node.L = prev; node.R = first; prev.R = node; first.L = node; }
prev = node;
});
});
function cover(col) {
col.R.L = col.L; col.L.R = col.R;
for (let i = col.D; i !== col; i = i.D)
for (let j = i.R; j !== i; j = j.R) { j.D.U = j.U; j.U.D = j.D; j.col.size--; }
}
function uncover(col) {
// exact reverse of cover: same nodes, opposite traversal order — see Pitfalls
for (let i = col.U; i !== col; i = i.U)
for (let j = i.L; j !== i; j = j.L) { j.col.size++; j.D.U = j; j.U.D = j; }
col.R.L = col; col.L.R = col;
}
const partial = [];
function search() {
if (header.R === header) return true; // no columns left uncovered — solved
let col = header.R;
for (let c = header.R; c !== header; c = c.R) if (c.size < col.size) col = c; // fewest candidates first
if (col.size === 0) return false; // dead end
cover(col);
for (let r = col.D; r !== col; r = r.D) {
partial.push(r.row);
for (let j = r.R; j !== r; j = j.R) cover(j.col);
if (search()) return true;
for (let j = r.L; j !== r; j = j.L) uncover(j.col); // reverse order — load-bearing
partial.pop();
}
uncover(col);
return false;
}
return search() ? partial : null;
}The column-choice rule isn't cosmetic — it's the branching factor. On this page's own 6-row matrix, covering the column with fewest live candidates first reaches the unique solution in 4 attempts and 1 backtrack; always covering the leftmost column instead needs 5 attempts and 2 — a small gap on a small matrix, but the same effect scales the way Sudoku's own MRV-vs-reading-order comparison does, only further, because here the choice sets how many candidate rows the very next branch has to try, not just which cell goes first. Built a fixed, reproducible 70-row, 20-column instance with a planted solution and ran both rules on the identical matrix, from this page's own reference implementation: leftmost-first needs 144,436 attempts to find a solution; fewest-candidates-first needs 10 — a difference of four orders of magnitude, computed directly, not estimated. Both rules are still correct; only the cost differs. That's the same "order can only cost speed, not the answer" lesson every other Backtracking entry on this site has already shown — Dancing Links just makes the gap enormous because the column choice controls branching width at every single level of the search, not just one.
Uncovering out of order silently returns an invalid answer. This is a genuinely new
failure mode none of the other nine Backtracking entries can have, because none of them undoes
through a linked structure. uncover must walk the exact same nodes cover
touched, in the exact reverse order — restoring column j3 before j2 before
j1 if they were covered j1, j2, j3. The reason is that covering
j2 can itself remove a row from j3's list before j3 is ever
covered; restoring j3 first, before that row is put back, silently reconstructs a
different (and wrong) matrix than the one that actually existed. Tested directly: took this page's own
uncover loop and restored columns in the same order they were covered instead of
reverse, then ran it across 2,000 random solvable instances. It never crashed and never got visibly
stuck — it just occasionally lied. Twice in 2,000 trials it returned a row selection presented as a
solved exact cover that wasn't one: one case selected six rows that left item 5 covered by two of them
at once, not once. Silently wrong, not silently slow, and with no error or warning anywhere in the
output to flag it — the same class of bug N-Queens' own Pitfalls section named first for this site,
now with an extra rule (order, not just "undo at all") because a linked structure can be relinked
wrong in a way a simple array pop can't.
Time: exponential in the worst case, same as every other entry in this category —
exact cover is NP-complete in general (it contains exact cover by 3-sets, one of the classical
NP-complete problems, as a restricted special case), so no column-choice rule changes the underlying
order, only the constant factor (see Pitfalls for how large that constant-factor difference actually
gets). What Dancing Links changes isn't the exponent, it's the cost of each individual cover/uncover:
O(k) pointer updates for a row/column pair touching k ones total, versus the
O(rows × columns) a naive Algorithm X would pay to copy or rescan the matrix on every
single cover and every single undo. Space: O(number of 1s in the
matrix) nodes, fixed for the entire search — covering and uncovering only relink existing
nodes, they never allocate or free one, so memory use doesn't grow with recursion depth or shrink on
backtrack.
Sudoku is a textbook exact-cover instance: one row per (cell, digit) placement, one column per constraint (every cell filled once; every row, column, and 3×3 box has each digit once) — this is the standard technique real Sudoku solvers use instead of the direct cell-by-cell search Sudoku builds on this site, and this page doesn't build that reduction, only the toy example above. See Choosing a Backtracking Strategy for how this page's linked-list undo compares to the other nine entries' plain array/grid undo.