# Exact cover and dancing links

> Eternity II states cleanly as an exact-cover problem, and Knuth's Algorithm X with dancing links is the classic machine for those. Where it genuinely shines (small boards, exhaustive counting) and the two reasons it does not crack the 16×16: an unshrunk search tree, and no partial credit.

- Canonical page (with interactive figures/demos): https://eternity2.dev/research/build/exact/exact-cover-dlx/
- Updated: 2026-07-02
- Topics: exact-methods
- Source: Knuth 2000, "Dancing Links" (arXiv cs/0011047) — https://arxiv.org/abs/cs/0011047
- Source: Knuth's Algorithm X (Wikipedia) — https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
- Source: Exact cover (Wikipedia) — https://en.wikipedia.org/wiki/Exact_cover

---
Some puzzles have to be bent to fit a formalism; Eternity II drops into exact
cover almost by itself. An exact-cover problem asks: given a set of items and
a collection of options, each option covering some items, pick options so that
every item is covered *exactly once*. Pentomino tilings, sudoku and the
n-queens problem are the textbook customers, and edge matching is next door.

## The board as an exact cover

Take 512 items: one per cell ("cell $c$ is filled") and one per piece
("piece $p$ is used"). Each option is a concrete placement, piece $p$ at
cell $c$ in rotation $r$, covering exactly two items, its cell and its
piece. A selection of options covering every item exactly once is precisely a
board with every cell filled and every piece used once.

What pure exact cover cannot say is that touching edges must agree. Knuth's
own extension handles it: XCC, exact covering with colours, where secondary
items (here, one per interior edge of the grid) carry a colour, and two
options may share a secondary item only if they assign it the same colour. A
full XCC solution is then exactly a perfect Eternity II board. The encoding
is faithful: nothing about the puzzle is approximated away.

## Algorithm X, and why the links dance

Knuth's Algorithm X solves exact cover by disciplined trial and error: pick
the item with the fewest remaining options (the fail-first rule), try each
option that covers it, remove everything that option makes impossible, and
recurse; on failure, restore and try the next.

Dancing links (DLX) is the data structure that makes the restore step
beautiful. The matrix of options lives in circular doubly linked lists, and
removing an element is two pointer writes, `left.right = right;
right.left = left`, which leaves the removed node's own pointers
intact. Undoing the removal is the same two writes reversed. Backtracking
becomes pointer surgery with zero copying, and the memory touched is exactly
proportional to work done. It is one of the most elegant algorithms in the
combinatorial toolbox, and Knuth's paper is a genuine pleasure to read.

## Watch the links dance

Here is the complete search on the exact instance Knuth uses in the paper:
seven items A–G, six options R1–R6, exactly one solution. Step through it and
watch the three moves that make up the whole algorithm: choose the emptiest
column, cover it (columns and rows detach from the lattice), and, on failure,
uncover in reverse (the same links splice back). The dead end at column E is
the moment worth stepping slowly: everything the wrong guess removed comes
back in exactly the opposite order, for two pointer writes per link.

> **[Figure]** Interactive: dancing links cover and uncover — interactive: DancingLinksLab. Rendered on the canonical page (link above); not shown in this markdown export.

Note what never happens: no copying, no rebuilding, no scanning for what to
restore. The removed nodes keep their own pointers while detached, and that
is the entire trick, so undoing a cover is as cheap as doing it.

## Step by step

The same run, in words. The matrix is R1 \{C,E,F\}, R2 \{A,D,G\}, R3 \{B,C,F\},
R4 \{A,D\}, R5 \{B,G\}, R6 \{D,E,G\}:

1. **Choose column A.** Two live options, tied for fewest; fail-first says
   branch on the most constrained item. Try its first option, R2 \{A,D,G\}:
   cover columns A, D and G. Every row touching them (R2, R4, R5, R6)
   detaches.
2. **Recurse.** Only R1 and R3 survive. Column B now has a single live
   option, so choose it, try R3 \{B,C,F\}: cover B, C, F, which detaches R1.
3. **Dead end.** Column E is still uncovered and no live option covers it.
   This branch can never complete, so no deeper search is even attempted.
4. **The dance.** Uncover F, C, B, then G, D, A, exact reverse order, each
   restoration the mirror image of the removal. The matrix is bit-for-bit
   back to its initial state, without having been saved anywhere.
5. **Try A's other option, R4 \{A,D\}.** Cover A, D. Column E now has exactly
   one live option, R1 \{C,E,F\}: cover C, E, F. Column B has one option left,
   R5 \{B,G\}: cover B, G.
6. **No columns remain**, every item covered exactly once. Solution:
   R1 + R4 + R5, found at depth 3 with a single dead end. The search then
   unwinds fully, verifies no other branch exists, and reports exactly one
   solution, and that certainty of exhaustion is the whole product.

## What it costs

The ledger has two very different lines:

- **The problem is NP-complete.** Exact cover is on Karp's original 1972
  list, so no polynomial algorithm is known for it, and Algorithm X is
  exponential in the worst case: it is a complete backtracking search, and
  its tree can grow like the product of the branching at each level.
- **The data structure is what's cheap.** DLX makes each link removal and
  each restoration $O(1)$: two pointer writes, with an exact undo, so the
  total time is $O(1)$ per link touched, proportional to the tree the search
  actually explores. Dancing links buys a superb constant factor and zero
  restore cost; it does not shrink the tree by a single node.

On Eternity II's scale: the XCC matrix itself is perfectly manageable, with 512
primary items (256 cells + 256 pieces), 480 secondary items for the interior
edges and their 22 colours, and at most $256 \times 256 \times 4 = 262{,}144$
options before symmetry and border pruning. Building it is minutes of work.
The tree above it is the wall: with [no forced moves](/research/why/no-forced-moves)
the branching stays wide all the way down, over a space usually estimated
near $10^{100}$, and $O(1)$ per node times an astronomical node count is
still astronomical. That is the precise sense in which DLX is the right tool
for small boards and the wrong weapon for the 16×16.

## Where it shines

DLX is the right tool when you want *all* solutions, or a count, or a proof
of uniqueness, on instances small enough to exhaust. On small edge-matching
boards it does exactly that: complete enumeration with excellent constant
factors, no solution missed, no state repeated. Counting complete tilings of
clue-sized regions, verifying that a generated mini-puzzle has a unique
solution, cross-checking another solver's exhaustive counts: this is its
home turf, and nothing heuristic competes there.

One project note from the trenches, offered as a warning rather than a
result: a from-scratch XCC implementation here validated cleanly on n-queens
and trivial boards, then spent days broken on anything larger, because the
interaction between colour-driven purification and cover/uncover restoration
is genuinely subtle. If you build it, follow Knuth's published algorithm to
the letter; the days lost above were this project's own to lose.

## Why it does not crack the 16×16

Two independent walls, either of which would suffice.

**The tree is the same tree.** Exact cover re-describes the search; it does
not shrink it. The fail-first item choice is a good variable ordering, but
[no move is ever forced](/research/why/no-forced-moves) on this puzzle: the
least-covered item still offers dozens of live options deep into the search,
so the branching stays enormous all the way down, over a space usually
estimated near $10^{100}$ boards. A DLX engine walks that tree completely or
not usefully at all; and its pointer-chasing inner loop is memory-bound,
an order of magnitude behind the cache-tuned array engines the
[record backtrackers](/research/lab/experiments/joshua-blackwood/solver) use.

**No partial credit.** DLX answers one question: covered exactly, or not.
The entire Eternity II economy runs on partial scores (467, 469, 470)
and on searches that deliberately tolerate a few mismatched edges to get
there. Exact cover has no native way to leave an edge unmatched and pay a
penalty; relaxing it that far means rebuilding it into a branch-and-bound,
at which point the elegance that justified it is gone.

## Verdict

Keep DLX on the shelf for what it is: the exhaustive instrument. Counting,
uniqueness proofs, ground truth on small boards: unbeatable, and worth the
implementation care it demands. As an attack on the full puzzle it is a
[dead end](/research/build/dead-ends), for structural reasons no constant
factor will fix: the tree it must exhaust is astronomical, and the
partial-score game every record method plays is one it cannot enter.

## Related

- [Dead ends](https://eternity2.dev/research/build/dead-ends) — Approaches we tried that look promising and don't move the needle on Eternity II, written down with what we found so you can spend your time elsewhere.
- [No forced moves](https://eternity2.dev/research/why/no-forced-moves) — The usual way to crack a logic puzzle is to find a spot where only one piece fits, place it, and repeat. That lever doesn't exist here: every interior piece has between 73 and 137 possible neighbours, and not one is ever pinned to a single option.
- [Blackwood's solver, decoded and run here](https://eternity2.dev/research/lab/experiments/joshua-blackwood/solver) — Joshua Blackwood's record backtracker, decoded through Jef Bucas's notes (a colour quota schedule and a late-game mismatch allowance, tuned near-optimally), then built and run on my M1: left as published it flies to 248 of 256 pieces ignoring the clues; pin the five official clues and the same engine stalls near 45.