Algorithm X

Purpose: Solve exact cover — given a 0/1 matrix, choose a set of rows so that every column contains exactly one 1. Knuth’s Algorithm X is the backtracking recipe; Dancing Links is the data structure that makes it fast.

Algorithm

AlgorithmX(matrix):
    if the matrix has no columns:
        the current partial solution is a complete exact cover — report it
    choose a column c with the fewest 1s          (the S-heuristic)
    if c has no 1s: backtrack (dead end)
    for each row r with a 1 in column c:
        add r to the partial solution
        for each column j where r has a 1:
            for each row i with a 1 in column j:
                delete row i
            delete column j
        recurse on the reduced matrix
        restore the deleted rows and columns
        remove r from the partial solution

Two things make this work in practice:

Choosing the most-constrained column (fewest remaining 1s) collapses the search tree enormously — it is the classic minimum-remaining-values heuristic.
Undoing deletions must be $O (1)$ , which is exactly what Dancing Links provides.

Paradigm

Backtracking / depth-first search with constraint propagation. Deleting a row-column pair is the propagation.

Complexity

Exponential in the worst case — exact cover is NP-complete. In practice the S-heuristic plus DLX solves problems that look hopeless: a hard Sudoku in well under a millisecond, an $8 \times 8$ pentomino tiling in seconds.

Modelling: turning a problem into exact cover

The whole skill is writing down the right matrix. Columns are constraints, rows are choices.

Sudoku — 324 columns, 729 rows:

Constraint group	Columns	Meaning
Cell	81	cell $(r, c)$ is filled exactly 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 of the matrix is a triple “place digit $d$ at $(r, c)$ ” and has exactly four 1s, one per constraint group.

N-Queens — 2 primary column groups (each rank, each file exactly once) and 2 secondary groups (each diagonal at most once). 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) plus one column per piece (must be used once); one row per legal placement.

Variants / Use Cases

Dancing Links (DLX) — the implementation; see that page for the code
Exact cover with optional (secondary) columns — for constraints that are “at most once”
Generalised / multiplicity cover (XCC) — Knuth’s later extension with colours and multiplicities
Exact Cover — the topic page with more modelling examples
Set cover — the minimisation cousin; NP-hard to approximate better than $ln n$ , see greedy approximations
SAT solvers — an alternative encoding route; often faster on large industrial instances, slower on tiling puzzles

whoashish's cp notes

Directory