Exact Cover

Imagine a grid of columns you must fill. You are handed a pile of rows, each row marking a few of the columns. Your job sounds easy: pick a handful of rows so that every column is covered exactly once — no column left empty, no column covered twice.

That single rule — exactly once — is the whole game. It is the abstract heart of fitting pentominoes into a board (every cell filled once, no overlaps) and of solving a Sudoku (every cell, row, column and box satisfied exactly once). Phrase the puzzle as columns-and-rows and these all become the same problem: exact cover.

The catch is the same one that haunts so much of computer science. Checking a proposed set of rows is instant. Finding one, in the worst case, can force you to wander through an exponential thicket of combinations.

Below is a small board and a set of pieces. Each piece is a row; each board cell is a column. A valid solution is a set of pieces that covers every cell exactly once — a perfect tiling with no gaps and no overlaps.

<p class="hint">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>
<div class="legend" id="legend"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.board { display: grid; grid-template-columns: repeat(6, 44px); gap: 3px; margin: .4rem 0; }
.cell { width: 44px; height: 44px; border-radius: 7px; background: #e6e9ee;
        border: 1px solid #cfd5dd; transition: background .15s, transform .12s; }
.cell.try { transform: scale(.84); outline: 2px dashed #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; color: #1d3557; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }
.legend { display: flex; gap: .6rem; flex-wrap: wrap; margin-top: .7rem; font-size: .82rem; color: #555; }
.legend span { display: inline-flex; align-items: center; gap: .35rem; }
.legend i { width: 14px; height: 14px; border-radius: 4px; display: inline-block; }

// Code not found

Press Solve (Algorithm X) and watch the solver work. It repeatedly picks the hardest-to-fill cell, tries each piece that could cover it, removes everything that piece conflicts with, and recurses — backing up the instant it gets stuck. The step counter shows how few placements it actually tries: this is the magic of Knuth's Dancing Links, which makes the removing-and-restoring almost free.

Where does exact cover sit on the map of hardness?

• Checking is trivial: given a set of chosen rows, verify that each column is covered exactly once. Linear time.
• It is NP-complete. Exact cover (in its X3C form, "exact cover by 3-sets") appears on Richard Karp's famous 1972 list of 21 NP-complete problems. So in the worst case nobody knows a method essentially faster than searching, and a fast general algorithm would settle P vs NP.
• Brute force would try every subset of rows — $2^{n}$ of them. Hopeless past a few dozen rows.
• Algorithm X + Dancing Links. In 2000 Donald Knuth popularized Algorithm X, a clean recursive backtracking search, implemented with a doubly-linked structure he called Dancing Links (DLX). The trick: when you tentatively pick a row, you unlink every conflicting row and column from a circular linked list; when you backtrack, those nodes "dance" right back into place in $O(1)$. The strategy of always branching on the column with the fewest options prunes the tree so aggressively that Sudokus and pentomino tilings fall in milliseconds.

The lesson is the one that runs through all of complexity: NP-complete is a worst-case verdict, not a death sentence. A worst-case-exponential problem can still have a brilliant practical algorithm — the difficulty just reappears as adversarial instances designed to make even DLX crawl. Exact cover is the textbook example of that gap between worst case and practice.

"Cover everything exactly once" is a surprisingly common shape, and recognizing it lets you reuse one excellent solver:

• Sudoku and logic puzzles: a Sudoku is an exact-cover instance with four kinds of constraints (cell, row, column, box). The fastest hand-written solvers are DLX underneath.
• Polyomino tiling: fitting pentominoes, tetrominoes or any shapes into a region — the demo above — is exact cover where columns are board cells and rows are legal placements.
• Scheduling and assignment: partitioning crews, shifts or tasks so each duty is covered once and nobody is double-booked is set partitioning, exact cover's industrial cousin.
• Combinatorial design: building error-correcting codes, Steiner systems and balanced experiments often comes down to finding exact covers.

Spot the "exactly once" structure and you inherit decades of tuning. Exact cover is the friendly twin of set cover and a close relative of SAT — recognize it and a hard-looking puzzle becomes a solved one.

Exact cover is a small, elegant question — pick rows that cover every column exactly once — that turns out to be NP-complete, sitting among Karp's original 21 hard problems. By the worst-case rulebook, that should make it frightening.

And yet Knuth's Dancing Links lets a laptop tile boards and crack Sudokus before you blink. That is the quiet moral of so much of this field: a problem can be provably hard in the worst case and routinely easy in practice, and the whole drama of P vs NP lives in the gap between those two sentences. Exact cover is where you can watch that gap close, one dancing link at a time.