Exact Cover

Given a universe $U$ and a family of subsets, choose a subfamily so that every element is covered exactly once. NP-complete (one of Karp’s 21).

Equivalently: given a 0/1 matrix, select rows so that every column contains exactly one 1.

Solving it

Algorithm X — backtracking with two decisions that make it fast:

Branch on the most-constrained column (the one with the fewest 1s). This is MRV, and it collapses the search tree.
Undo in $O (1)$ using Dancing Links (DLX), where removing and restoring a doubly linked node are both two pointer writes.

AlgorithmX(matrix):
    if no columns remain: report the solution
    c = column with the fewest 1s
    if c has no 1s: backtrack
    for each row r with a 1 in c:
        add r to the solution
        cover every column in which r has a 1 (removing conflicting rows)
        recurse
        uncover, remove r

Modelling — the actual skill

Columns are constraints, rows are choices.

Each row must have a 1 in exactly the constraints its choice satisfies.

Sudoku — 324 columns, 729 rows

Constraint group	Columns	Meaning
Cell	81	cell $(r, c)$ is filled once
Row	81	digit $d$ appears once in row $r$
Column	81	digit $d$ appears once in column $c$
Box	81	digit $d$ appears once in box $b$

Each row is “place digit $d$ at $(r, c)$ ” with exactly four 1s. DLX solves the hardest known puzzles in microseconds.

N-Queens

Primary columns (exactly once): each rank, each file.
Secondary columns (at most once): each diagonal.

Secondary columns are the “exact cover with optional columns” generalisation — they may be left uncovered.

Polyomino tiling

One column per board square (must be covered once).
One column per piece (must be used once, if pieces are distinct).
One row per legal placement (position × orientation).

This is the canonical DLX application, and it solves pentomino packings that resist ad-hoc search.

Other encodings

Problem	Columns	Rows
Latin squares	cell, row-symbol, column-symbol	place symbol at cell
Perfect matching	each vertex	each edge
Set partitioning	each element	each candidate set
Langford pairs	each position, each number	each placement
Instant Insanity	each cube, each face-colour constraint	each orientation

Exact cover vs set cover

	Exact cover	Set cover
Requirement	each element exactly once	each element at least once
Objective	feasibility (or count)	minimise the number of sets
Approximation	not meaningful	$ln n$ greedy, and that is optimal
Method	DLX / Algorithm X	greedy, ILP

They look similar and behave completely differently. Exact cover is a constraint satisfaction problem; set cover is an optimisation problem.

Variants

With optional (secondary) columns — “at most once” constraints, as in N-Queens diagonals.
XCC (exact cover with colours) — Knuth’s TAOCP 4B extension, where secondary columns carry a colour and multiple rows may share one if the colours agree. Handles puzzles with compatibility constraints.
Multiplicities — a column must be covered between $l$ and $u$ times.
Counting solutions rather than finding one — the same search, no early exit.

When to use DLX

Signal
The problem is naturally “cover every requirement exactly once”	✔
Choices are enumerable and each satisfies a fixed small set of constraints	✔
Puzzle-like: tiling, placement, filling	✔
The constraint matrix is sparse	✔
It is an optimisation, not a feasibility, problem	✘ — use ILP or branch and bound
The constraints are boolean clauses	✘ — use SAT

For contest use, a hand-written backtracking search with MRV usually suffices; DLX earns its place when the same solver must handle many instances or the naive search is too slow.

See also: Algorithm X · Dancing Links · Backtracking

whoashish's cp notes

Directory