iv. Exact Cover and Dancing Links

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.

Algorithm X

Knuth’s backtracking recipe, with two decisions that make it fast:

AlgorithmX(matrix):
    if no columns remain: report the solution
    c = column with the fewest 1s                 (the S-heuristic: minimum-remaining-values)
    if c has no 1s: backtrack (dead end)
    for each row r with a 1 in c:
        add r to the solution
        cover every column where r has a 1 (removing conflicting rows from all of them)
        recurse
        uncover, remove r

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

Proof: Algorithm X is correct

Soundness. A reported solution is exactly the set of rows added to solution across a path that reaches “no columns remain” — meaning every column was covered by the covering operations triggered by exactly the chosen rows, and cover removes exactly the rows that would conflict (share a column) with the chosen row, so no two chosen rows ever share a column; every column ends up covered exactly once.
Completeness. Fix any column $c$ (the algorithm always picks one that still needs covering). In any valid exact cover, exactly one row covers $c$ (by definition of exact cover). So branching over every row with a 1 in $c$ and recursing is exhaustive: every valid exact cover is reached through the branch corresponding to whichever row it uses to cover $c$ . Choosing $c$ to be the most-constrained column (fewest 1s) doesn’t change which covers are reachable — it only changes the branching factor at this step, since every valid solution must still pick one of $c$ ‘s rows regardless of which column is chosen first. $■$

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 x 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”	yes
Choices are enumerable and each satisfies a fixed small set of constraints	yes
Puzzle-like: tiling, placement, filling	yes
The constraint matrix is sparse	yes
It is an optimisation, not a feasibility, problem	no — use ILP or branch and bound
The constraints are boolean clauses	no — 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.

Dancing Links

The data structure (Knuth, “DLX”) that makes Algorithm X fast: a sparse 0/1 matrix stored as a toroidal doubly linked list, in which removing and restoring a node are both $O (1)$ .

The core trick

In a doubly linked list, removing node $x$ sets x.left.right = x.right and x.right.left = x.left. But $x$ itself still points at its old neighbours — so restoring it is just x.left.right = x and x.right.left = x. No allocation, no stack of saved values, no copying. Knuth called the effect “dancing” because the pointers seem to leap out and back.

Proof: uncover must reverse cover's exact order

Covering column $c$ unlinks a sequence of nodes $n_{1}, n_{2}, \dots, n_{k}$ (in the order cover’s loop visits them). Each unlink only modifies the pointers of $n_{i}$ ‘s current neighbours at the time — which may themselves have already been unlinked earlier in the same pass if they belong to an overlapping row. Restoring in the same order would try to relink $n_{1}$ against neighbours that, by the time $n_{1}$ is restored, have already had pointers changed by later operations in a way $n_{1}$ ‘s own stale neighbour-pointers don’t account for. Restoring in reverse order guarantees that when $n_{i}$ is relinked, every node unlinked after $n_{i}$ (hence relinked before it, in reverse order) is already back in place, so $n_{i}$ ‘s stored neighbour pointers (which still point to its state at the moment it was unlinked) are accurate again. This is the standard “undo a stack of operations in reverse” argument, specialised to pointer surgery. $■$

Array-based DLX — the practical version

Six parallel int arrays (L,R,U,D,C) indexed by node id, plus a per-column size, instead of allocated pointer nodes: same algorithm, far better cache behaviour, no allocator pressure — this is what competitive implementations do.

struct DLX {
    vector<int> L, R, U, D, C, rowOf;
    vector<int> size;
    int nCols;
 
    DLX(int nCols_) : nCols(nCols_) {
        int total = nCols + 1;                     // node 0 is the root; nodes 1..nCols are column headers
        L.resize(total); R.resize(total); U.resize(total); D.resize(total); C.resize(total); rowOf.assign(total, -1);
        size.assign(nCols + 1, 0);
        for (int i = 0; i <= nCols; i++) { L[i] = i - 1; R[i] = i + 1; U[i] = D[i] = i; C[i] = i; }
        L[0] = nCols; R[nCols] = 0;
    }
 
    void addRow(int rowId, const vector<int>& cols) {   // cols: 1-indexed column ids, this row's 1s
        int first = -1, prev = -1;
        for (int c : cols) {
            int node = L.size();
            L.push_back(0); R.push_back(0); U.push_back(U[c]); D.push_back(c); C.push_back(c); rowOf.push_back(rowId);
            D[U[c]] = node; U[c] = node;
            size[c]++;
            if (first == -1) first = node;
            if (prev != -1) { L[node] = prev; R[prev] = node; }
            prev = node;
        }
        if (first != -1) { L[first] = prev; R[prev] = first; }
    }
 
    void cover(int c) {
        R[L[c]] = R[c]; L[R[c]] = L[c];
        for (int i = D[c]; i != c; i = D[i])
            for (int j = R[i]; j != i; j = R[j]) { U[D[j]] = U[j]; D[U[j]] = D[j]; size[C[j]]--; }
    }
    void uncover(int c) {
        for (int i = U[c]; i != c; i = U[i])
            for (int j = L[i]; j != i; j = L[j]) { size[C[j]]++; U[D[j]] = j; D[U[j]] = j; }
        R[L[c]] = c; L[R[c]] = c;
    }
 
    vector<int> sol;
    bool search() {                                 // finds one solution; sol holds the chosen row ids
        if (R[0] == 0) return true;                 // no columns left: every constraint covered
        int c = R[0];
        for (int j = R[0]; j != 0; j = R[j]) if (size[j] < size[c]) c = j;
        if (size[c] == 0) return false;              // dead end: an uncoverable column
        cover(c);
        for (int r = D[c]; r != c; r = D[r]) {
            sol.push_back(rowOf[r]);
            for (int j = R[r]; j != r; j = R[j]) cover(C[j]);
            if (search()) return true;
            for (int j = L[r]; j != r; j = L[j]) uncover(C[j]);
            sol.pop_back();
        }
        uncover(c);
        return false;
    }
};

Complexity: cover/uncover are $O (nodes in the affected rows)$ , no hidden constant; the overall search is exponential in the worst case (exact cover is NP-complete), but the S-heuristic keeps real instances fast — a hard Sudoku in well under a millisecond, pentomino packings in seconds.

Proof: search finds a true exact cover, and terminates

This is Algorithm X verbatim (proved above) with cover/uncover implementing the column/row deletion and restoration in $O (1)$ amortised per node touched (proved above). R[0]==0 means the column header ring is empty — every column has been covered by some chosen row, exactly the exact-cover condition. size[c]==0 for the chosen (most-constrained) column means no row can cover it, so this branch of the partial solution is infeasible and the function correctly backtracks (returning false after restoring, via the loop’s own uncover calls, every column it had covered). Termination: each recursive call either succeeds immediately, exhausts column $c$ ‘s rows (a strictly smaller search), or finds a dead end — the recursion depth is bounded by the number of columns (each level covers at least one more column), and the total work is finite since the underlying matrix is finite. $■$

Tested: DLX checked against brute-force exact cover search (try every subset of rows, $2^{rows}$ ) on small random 0/1 matrices, including matrices with no solution, exactly one, and several; and used to solve a full Sudoku puzzle (729 rows, 324 columns, as in the modelling table above) with the result cross-checked against the backtracking Sudoku solver’s answer.

Variants / Use Cases

Sudoku solvers — the canonical demo; solves the hardest known puzzles in microseconds.
Polyomino / pentomino tiling, N-Queens, Latin squares, Langford pairs.
XCC (exact cover with colours) — Knuth’s extension in TAOCP Volume 4B, for puzzles with compatibility constraints.
Any backtracking with heavy undo — the dancing-links idea generalises to rollback DSU, persistent structures, and undo-able segment trees.
Set cover — the minimisation cousin; NP-hard to approximate better than $ln n$ , see greedy approximations.

whoashish's cp notes

Directory