Dancing Links (DLX)

Exact cover is a deceptively simple question: given a universe of items and a collection of sets, can you choose a sub-collection such that every item appears in exactly one chosen set? No gaps, no overlaps — perfect coverage.

The puzzle appears everywhere. Can twelve pentomino pieces tile a 6×10 rectangle with no overlap? Can 81 Sudoku cells be filled so each digit covers each row, column, and box exactly once? Both reduce to exact cover, and exact cover is NP-complete.

In 2000, Donald Knuth published "Dancing Links" — a paper that shows how to solve exact-cover problems with breathtaking efficiency. The key insight is not an algorithmic trick but a data-structure one: represent the constraint matrix as a doubly-linked toroidal list, then implement backtracking by unlinking and relinking nodes. When a search branch fails and you need to undo, deleted nodes dance back into place — each node still knows its old neighbors even while removed, so restoration is O(1) per node.

The board below is a 4×5 grid (20 cells). We use four of the twelve standard pentominoes — L, P, N, U — each covering exactly 5 cells (4 × 5 = 20 total), with no overlap and no gap. Fitting them perfectly is an exact-cover problem.

<p class="hint">{{hint}}</p>
<div id="grid"></div>
<div class="info-row">
  <span class="label">{{label_placements}} <b id="steps">0</b></span>
  <span id="msg" class="label bold">{{press_step_or_solve}}</span>
</div>
<div class="btns">
  <button id="btn-step">{{btn_step}}</button>
  <button id="btn-solve">{{btn_solve}}</button>
  <button id="btn-reset" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#grid { display: grid; grid-template-columns: repeat(5, 46px); gap: 3px; margin: .4rem 0; }
.cell { width: 46px; height: 46px; border-radius: 7px; border: 1px solid #bcc5ce;
        background: #e8eef3; transition: background .15s; display: flex;
        align-items: center; justify-content: center;
        font: 700 14px ui-monospace, monospace; color: rgba(0,0,0,.4); }
.c-L { background: #e63946; color: #fff; border-color: #c92f3c; }
.c-P { background: #2a9d8f; color: #fff; border-color: #1f7d71; }
.c-N { background: #e9c46a; color: #555; border-color: #c9a450; }
.c-U { background: #a8dadc; color: #1d3557; border-color: #80bdbf; }
.info-row { display: flex; gap: 1rem; align-items: center; font-size: .9rem;
            margin: .35rem 0; flex-wrap: wrap; }
.label { color: #444; }
.bold { font-weight: 600; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Press Step to watch DLX pick the cell covered by the fewest placements (S heuristic), select a row (piece placement) that covers it, recursively solve the rest, and backtrack when stuck. Press Solve to find the complete solution at once. The counter shows how many placements DLX tried — exact cover is NP-complete, but the right data structure keeps the constant factor tiny.

Exact cover is NP-complete — proven by reduction from 3-dimensional matching. That means no polynomial-time algorithm is known, and for the worst inputs you cannot avoid exponential search. So where does DLX's speed come from?

• Algorithm X (Knuth 2000) is a systematic backtracking search. At each step it picks an uncovered column (constraint), tries every row that covers it (choice), recursively solves the reduced problem, and backtracks on failure. The correctness is trivial; the cost is the branching factor times the recursion depth.
• The S heuristic: always choose the column with the fewest rows covering it ("minimum remaining values"). This prunes the search tree dramatically — a column with zero options is detected immediately; one with only two options limits branching to 2.
• O(1) cover/uncover: because nodes remain in memory and still hold their old left/right/up/down pointers, removing a node from a list is four pointer writes, and restoring it is four more. No heap allocation, no searching — just pointer gymnastics. This is the dancing in Dancing Links.
• Empirical speed: DLX finds solutions to millions-of-cell Sudoku puzzles and pentomino tilings in milliseconds, even though the problem class is NP-complete. The pruning and cache-friendly structure make the constant factor small enough for practical use.

The takeaway: NP-completeness characterizes worst-case behaviour on adversarial inputs. Real puzzles have rich structure that branch-and-bound with a good heuristic exploits heavily.

Exact cover sounds abstract, but it is the hidden shape of countless real problems:

• Puzzle solving: Sudoku, pentominos, polyomino tilings, N-queens, and Latin squares all reduce naturally to exact cover — DLX solves them faster than any other general method.
• Scheduling and timetabling: assign tasks to slots so each task gets exactly one slot and each slot holds exactly one task. This is exact cover. See also scheduling.
• Compiler register allocation: partition live variables into register groups so each variable is in exactly one group and no two conflicting variables share a group.
• DNA sequencing: shotgun assembly asks which fragments tile the genome exactly — an exact-cover formulation reduces the search space.
• Set partitioning in operations research: flight crew scheduling, vehicle routing, and warehouse order batching all use variants of exact cover solved by branch-and-price algorithms that share DLX's cover/uncover logic.

Understanding DLX means understanding how to turn a combinatorial explosion into disciplined search — the same skill that powers modern SAT solvers and constraint-programming engines.

Dancing Links is a masterclass in a principle that never goes out of style: choose your data structure first, then the algorithm writes itself. Exact cover is NP-complete, yet DLX tears through Sudoku puzzles and pentomino tilings in milliseconds because every backtrack step costs only a handful of pointer writes.

Knuth called the paper "Dancing Links" because the nodes literally dance — removed from a list, they still remember where they belong, and they glide back the instant the algorithm backtracks. It is a rare case where the implementation detail is also the most beautiful idea.

The next time you face a problem that smells like "cover everything exactly once," reach for DLX before reaching for despair. NP-completeness is a ceiling on the worst case — not a wall against good engineering.