Introduction

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.

Try It

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">Each board cell is a <b>column</b> to cover; each colored piece is a <b>row</b>. A solution chooses pieces so that <b>every cell is covered exactly once</b> — no gaps, no overlaps. Checking a tiling is instant; finding one is NP-complete.</p>
<div id="board" class="board"></div>
<div class="status" id="status">Press Solve to watch Algorithm X work.</div>
<div class="btns">
  <button id="solve" type="button">Solve (Algorithm X)</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// EXACT COVER, told as tiling. Board = 6x4 = 24 cells = the "columns" to cover.
// Each legal placement of a piece is a "row" that covers a set of cells.
// Algorithm X (Knuth, 2000): repeatedly pick the column (cell) with the FEWEST
// rows covering it, try each such row, mark its cells covered + its piece used,
// recurse, and backtrack the instant a column has no remaining row. Dancing
// Links makes the remove/restore O(1); here the same logic runs on bitmasks.
const W = 6, H = 4, NCELL = W * H;
const COLORS = ['#e63946','#2a9d8f','#e9c46a','#457b9d','#9b5de5','#f3722c'];
const idx = (r, c) => r * W + c;

// Six distinct connected tetrominoes that tile the 6x4 board exactly (verified).
const PIECES = [
  { name: 'T', cells: [[0,0],[0,1],[0,2],[1,1]] },
  { name: 'L', cells: [[0,0],[1,0],[2,0],[2,1]] },
  { name: 'F', cells: [[0,1],[1,0],[1,1],[2,1]] },
  { name: 'J', cells: [[0,0],[0,1],[1,0],[2,0]] },
  { name: 'Y', cells: [[0,1],[1,0],[1,1],[1,2]] },
  { name: 'P', cells: [[0,1],[1,0],[1,1],[2,1]] }
];

// ROWS = every legal placement (translation) of every piece on the board.
const ROWS = [];
PIECES.forEach((p, pi) => {
  const maxR = Math.max(...p.cells.map(c => c[0]));
  const maxC = Math.max(...p.cells.map(c => c[1]));
  for (let r = 0; r + maxR < H; r++)
    for (let c = 0; c + maxC < W; c++) {
      const cover = p.cells.map(([dr, dc]) => idx(r + dr, c + dc));
      ROWS.push({ piece: pi, color: COLORS[pi], cover, mask: cover.reduce((a, b) => a | (1 << b), 0) });
    }
});

// Algorithm X over the implicit matrix (columns = cells, rows = placements).
let steps = 0;
function algorithmX() {
  steps = 0;
  const FULL = (1 << NCELL) - 1;
  const rec = (mask, usedPieces) => {
    if (mask === FULL) return [];                 // all columns covered: done
    // Choose the uncovered cell with the fewest candidate rows (MRV heuristic).
    let bestRows = null;
    for (let col = 0; col < NCELL; col++) {
      if (mask & (1 << col)) continue;
      const rows = [];
      for (let ri = 0; ri < ROWS.length; ri++) {
        const row = ROWS[ri];
        if (usedPieces & (1 << row.piece)) continue;   // each piece used once
        if (!(row.mask & (1 << col))) continue;        // must cover this cell
        if (row.mask & mask) continue;                 // no overlap
        rows.push(ri);
      }
      if (rows.length === 0) return null;              // dead column: backtrack
      if (bestRows === null || rows.length < bestRows.length) bestRows = rows;
    }
    for (const ri of bestRows) {
      steps++;
      const sub = rec(mask | ROWS[ri].mask, usedPieces | (1 << ROWS[ri].piece));
      if (sub) return [ri, ...sub];
    }
    return null;
  };
  return rec(0, 0);
}

function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls || ''); }
function renderBoard() {
  const b = document.getElementById('board'); b.innerHTML = '';
  for (let i = 0; i < NCELL; i++) { const d = document.createElement('div'); d.className = 'cell'; b.appendChild(d); }
}
function renderLegend() {
  const l = document.getElementById('legend'); l.innerHTML = '';
  PIECES.forEach((p, i) => { const s = document.createElement('span'); s.innerHTML = fmt('<i style="background:%v%"></i>Piece %name%', { v: COLORS[i], name: p.name }); l.appendChild(s); });
}

function animate(rowIds) {
  const cells = document.getElementById('board').children;
  let k = 0;
  const tick = () => {
    if (k >= rowIds.length) {
      setStatus(fmt('Solved! Every cell covered exactly once — %steps% placements tried.', { steps: steps }), 'ok');
      document.getElementById('solve').disabled = false;
      return;
    }
    const row = ROWS[rowIds[k]];
    for (const c of cells) c.classList.remove('try');
    row.cover.forEach(ci => cells[ci].classList.add('try'));
    setTimeout(() => {
      row.cover.forEach(ci => { cells[ci].classList.remove('try'); cells[ci].style.background = row.color; });
      k++; tick();
    }, 300);
  };
  tick();
}

document.getElementById('solve').addEventListener('click', () => {
  renderBoard();
  document.getElementById('solve').disabled = true;
  setStatus('Searching with Algorithm X…');
  const sol = algorithmX();
  if (!sol) { setStatus('No exact cover exists for these pieces.', 'bad'); document.getElementById('solve').disabled = false; return; }
  console.log('Exact cover found:', sol.map(ri => PIECES[ROWS[ri].piece].name + '@[' + ROWS[ri].cover.join(',') + ']').join('  '));
  console.log('Placements tried (steps):', steps);
  animate(sol);
});
document.getElementById('reset').addEventListener('click', () => { renderBoard(); setStatus('Press Solve to watch Algorithm X work.'); });

renderLegend();
renderBoard();
Result
Console

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.

The Real Complexity

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 — 2n2^{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)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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/exact-cover/Content licensed under CC BY-NC 4.0.