Reducibility
Glossary Contents
← Ch XIII
Chapter XIV Exact Cover
Ch XV →
  1. 40 — Exactly once
  2. 41 — Algorithm X in Ruby
  3. 42 — Crew assignment, exactly
Chapter XIV

Exact Cover

Cover the universe so every element is covered exactly once by your chosen sets. The problem under Sudoku, polyomino tiling, and Knuth's Dancing Links.

40

Exactly once

Set cover is "at least once." Exact cover is "exactly once." That tiny change is the difference between a covering problem and a partitioning one.

Exact cover on a universe U and a family F asks for a subfamily that partitions U — every element appears in exactly one chosen set:

F∗⊆F,S∈F∗⋃​S=U,S∩T=∅  for all S=T∈F∗.(1)

The combination in (1) — both covering and disjointness — is what separates exact cover from its set-cover cousin. Karp showed it NP-complete.

Donald Knuth in 2000 published Algorithm X, a depth-first search with a particularly elegant data structure called Dancing Links (DLX), that solves the problem with very low overhead. DLX is fast in practice on Sudoku, polyomino tiling, exact-set-partitioning IPs, and pentomino puzzles.

Exact cover also sits at the heart of integer-programming set partitioning — the constraint "exactly one" instead of "at least one" comes up in airline crew assignment.

Figures, in plain terms
(1)

Three constraints joined by commas. Read each one in turn.

**F ⊆ F* picks a subfamily of the family — same subset symbol as before. The asterisk just decorates the name.

**⋃ S in F S = U* is the big-union covering condition, identical to set cover in chapter 6: every element of the universe must appear in at least one chosen set.

S ∩ T = ∅ for all S ≠ T ∈ F* is the disjointness condition from set packing in chapter 4: no two chosen sets share any element.

What makes exact cover special is that both conditions hold at once. The chosen sets cover everything (set-cover-like) and never overlap (set-packing-like). Together: each element appears in exactly one chosen set — a partition of U.

In plain terms

Cover every item with bundles, but each item must end up in exactly one bundle — not zero, not two. Sudoku is secretly an exact-cover puzzle: place a digit so each row, column, and box contains every digit exactly once.

Scan to come back to page 40

← 39 Community detection
1/3 · 40/63
41 Algorithm X in Ruby →