Algorithm X — Exact Cover

How Algorithm X works

Cast the problem as a 0/1 matrix. Rows are candidate options; columns are constraints. A 1 in cell (r, c) means option r satisfies constraint c. Goal: pick a set of rows so that every column has exactly one selected row with a 1.

Algorithm X(matrix):
    if matrix is empty:                          # every constraint satisfied
        record solution; return

    pick column c with the smallest count of 1s  # MRV heuristic
    if c.count == 0: return                      # constraint can't be satisfied → backtrack

    for each row r that has a 1 in column c:
        add r to partial solution
        cover c and every other column j where r has a 1:
            remove every row k that also has a 1 in column j
        recurse on the reduced matrix
        uncover, reversing the removes exactly
        remove r from partial solution

Three moving parts: choice (which column to focus on), commitment (which row to try), recovery (uncover on backtrack). The first is a heuristic that drives pruning. The second is a loop over candidate rows. The third is the reversible operation that makes the whole thing fast.

What "exact cover" really means

Given universe U = {1, 2, ..., m} and collection of subsets S = {S₁, S₂, ..., Sₙ} where each Sᵢ ⊆ U, find a subcollection S* ⊆ S such that:

• Every element of U appears in at least one set of S*.
• Every element of U appears in at most one set of S*.

Equivalently: the chosen sets partition U. The "exact" rules out both gaps (uncovered elements) and overlap (elements covered twice). In matrix form: each column must have exactly one selected row with a 1.

The problem is on Karp's original 1972 list of 21 NP-complete problems, alongside SAT, vertex cover, and Hamiltonian cycle. Reductions to and from exact cover are common: 3SAT reduces to exact cover, exact cover reduces to subset sum.

Trace: tiny exact-cover instance

      C1  C2  C3  C4  C5
R1:    1   0   1   0   0
R2:    0   1   0   1   0
R3:    1   0   0   0   1
R4:    0   1   1   0   1
R5:    0   1   0   1   1

Column counts: C1=2 (R1,R3), C2=3 (R2,R4,R5), C3=2 (R1,R4),
               C4=2 (R2,R5), C5=3 (R3,R4,R5)

Algorithm X picks min: C1 (count 2).

Try R1: covers C1, C3.
  Remove R1, R3 (both have 1 in C1).
  Remove R1, R4 (both have 1 in C3).
  Remove headers C1, C3.

  Remaining columns: C2, C4, C5
  Remaining rows: R2, R5
        C2  C4  C5
  R2:    1   1   0
  R5:    1   1   1

  Column counts: C2=2, C4=2, C5=1 — pick C5.
  Try R5: covers C5, also C2, C4 (all of R5's ones).
    Remove R5 (only row in C5).
    Remove R2 (has 1 in C2, also covered by R5).
    Remove headers C2, C4, C5.

    Matrix empty → SOLUTION: {R1, R5}

  Uncover. Try next row in C5 column: none. Backtrack.

  Restore C2, C4, C5; restore R1, R2, R3, R4, R5.

Back at top level. Try R3 instead of R1:
  R3 covers C1, C5.
  Remove R3, R1 (both in C1).
  Remove R3, R4, R5 (all in C5).
  Remaining: R2 alone, with columns C2, C3, C4.

  R2:  C2=1, C3=0, C4=1 — C3 has count 0 → BACKTRACK.

Uncover. No more rows in C1. Backtrack out of C1.
Done. One solution: {R1, R5}.

The search tree explored two top-level branches (R1, R3), one sub-branch (R5), and one immediate failure (R3 → empty C3). Five total nodes for a 5×5 matrix. The MRV heuristic kept the tree tiny by always picking the column where failure is fastest to detect.

When to use Algorithm X

• Constraint satisfaction with binary "satisfied / not satisfied" relations. If your problem reduces to "pick options to satisfy each constraint exactly once," Algorithm X is the canonical solver.
• Sparse constraint matrices. Each option (row) should satisfy only a handful of constraints (have a few 1s). Dense problems fit bit-vector solvers better.
• Need every solution, not just one. Algorithm X enumerates by default — useful for counting Sudoku solutions, generating tilings, or verifying uniqueness.
• Reversible state. The cover/uncover pattern works because state is fully restorable. If your constraints aren't reversible (e.g., dynamic costs), use a different approach.

For problems with continuous variables, soft constraints, or numerical optimization, Algorithm X doesn't apply. CSP solvers like MiniSAT and constraint-programming libraries (Gecode, OR-Tools) are the right tools then.

Algorithm X vs alternative solvers

	Algorithm X (DLX)	SAT solver	CSP solver	ILP solver	Brute-force backtrack	Greedy approx.
Specialization	Exact cover	CNF SAT	General constraints	Linear inequalities	Any	Set cover (not exact)
9×9 Sudoku	~5 ms	~20 ms (with encoding)	~10 ms	~100 ms	~500 ms	N/A (no exact guarantee)
16×16 Sudoku	~100 ms	~250 ms	~200 ms	~5 s	~30 s	N/A
Pentomino tiling	~3 s	~10 s	~5 s	~60 s	~30 min	N/A
Setup complexity	Low — encode matrix	Med — CNF encoding	Low — declarative	High — formulate LP	None	None
Best for	Sudoku, tiling, n-queens	Logic puzzles, verification	Scheduling, assignment	Optimization with linear ranges	Tiny problems	Approximate set cover

What "milliseconds" means in practice

Problem	Candidates	Constraints	Search nodes	DLX time
4×4 Sudoku	64	64	~30	~50 µs
9×9 Sudoku (average)	729	324	~5,000	~5 ms
9×9 Sudoku (AI Escargot)	729	324	~200,000	~30 ms
16×16 Sudoku	4,096	1,024	~100,000	~100 ms
25×25 Sudoku	15,625	2,500	~10⁶	~3 s
N-queens (n=18, count all)	~324	72	666 M solutions	~1 hour
Pentomino 6×10 tiling	2,000	72	~9 M	~3 s

The wall-clock numbers come from JVM-tuned DLX implementations on modern x86 hardware (e.g., Norvig's Common Lisp solver, the Java solvers used in Sudoku research papers). Python implementations run ~10× slower; well-tuned C is ~2× faster than Java.

The dramatic Sudoku speedup over naïve backtracking (~100×) comes from two sources: (1) the MRV heuristic that picks the most constrained cell first, often finding forced moves immediately, and (2) the O(1) cover/uncover from dancing links, which eliminates the recursion-level allocation cost.

JavaScript implementation

// Algorithm X using Dancing Links. Each row of the matrix is a candidate option;
// each column is a constraint.

function algorithmX(matrix, columnNames, onSolution) {
  const dlx = new DLX(columnNames);
  for (let r = 0; r < matrix.length; r++) {
    const ones = [];
    for (let c = 0; c < matrix[r].length; c++) if (matrix[r][c]) ones.push(c);
    dlx.addRow(r, ones);
  }
  dlx.search([], onSolution);
}

// Example: find all exact covers of the universe {1..5}
//   options = [{1,3}, {2,4}, {1,5}, {2,3,5}, {2,4,5}]
const matrix = [
  [1, 0, 1, 0, 0],  // R1 = {1, 3}
  [0, 1, 0, 1, 0],  // R2 = {2, 4}
  [1, 0, 0, 0, 1],  // R3 = {1, 5}
  [0, 1, 1, 0, 1],  // R4 = {2, 3, 5}
  [0, 1, 0, 1, 1],  // R5 = {2, 4, 5}
];

algorithmX(matrix, ['e1','e2','e3','e4','e5'], (rows) => {
  console.log('Solution:', rows.map(r => `R${r+1}`).join(', '));
});
// → Solution: R1, R5    (covers {1,3} ∪ {2,4,5} = {1,2,3,4,5})

For the DLX implementation itself, see the Dancing Links article — it contains the full ~80-line solver class that algorithmX uses.

Famous problem: Sudoku encoded as exact cover

To solve a 9×9 Sudoku with Algorithm X, encode it as an exact-cover matrix with four constraint families:

function sudokuToExactCover(puzzle) {
  // 729 candidate rows: (row r, col c, digit d) for r,c,d in 0..8 / 1..9
  // 324 constraint columns:
  //   - 81 "cell (r,c) is filled" columns
  //   - 81 "row r contains digit d" columns
  //   - 81 "col c contains digit d" columns
  //   - 81 "box b contains digit d" columns
  const rows = [], rowMeta = [];
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const given = puzzle[r][c];
      for (let d = 1; d <= 9; d++) {
        if (given !== 0 && given !== d) continue;
        const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
        rows.push([
          /* cell    */    r * 9 + c,
          /* row-d   */ 81 + r * 9 + (d - 1),
          /* col-d   */ 162 + c * 9 + (d - 1),
          /* box-d   */ 243 + b * 9 + (d - 1),
        ]);
        rowMeta.push({ r, c, d });
      }
    }
  }
  return { rows, rowMeta };
}

function solveSudoku(puzzle) {
  const { rows, rowMeta } = sudokuToExactCover(puzzle);
  const dlx = new DLX(Array.from({ length: 324 }, (_, i) => `c${i}`));
  rows.forEach((cols, i) => dlx.addRow(i, cols));
  let solution = null;
  dlx.search([], (rowIds) => { solution = rowIds; return true; }); // stop at first
  if (!solution) return null;
  const grid = Array.from({ length: 9 }, () => Array(9).fill(0));
  solution.forEach(rid => {
    const { r, c, d } = rowMeta[rid];
    grid[r][c] = d;
  });
  return grid;
}

The encoding has 729 rows × 324 columns × 4 ones per row = 2916 total ones, sparsity 1.2%. DLX visits ~5,000 search nodes on an average puzzle, ~200,000 on the hardest known. Wall-clock time is dominated by the cover/uncover work — but each operation is just pointer writes, so the constant factor is tiny.

Python implementation

def algorithm_x(matrix, column_names, find_all=False):
    """Returns list of solutions; each solution is a list of row indices."""
    dlx = DLX(column_names)
    for r, row in enumerate(matrix):
        ones = [c for c, v in enumerate(row) if v]
        dlx.add_row(r, ones)
    solutions = []
    dlx.search([], lambda sol: solutions.append(sol))
    return solutions if find_all else (solutions[:1] if solutions else [])

# N-queens as exact cover
def n_queens_exact_cover(n):
    """Build the exact-cover matrix for the n-queens problem."""
    rows, meta = [], []
    for r in range(n):
        for c in range(n):
            cols = [
                r,                   # row constraint (n columns)
                n + c,               # column constraint (n columns)
                2*n + r + c,         # \-diagonal (2n-1 columns, secondary)
                2*n + (2*n - 1) + (r - c + n - 1),  # /-diagonal (2n-1, secondary)
            ]
            rows.append(cols)
            meta.append((r, c))
    # Note: diagonals are "secondary" — they can be uncovered (≤1 not =1).
    return rows, meta

# For 8-queens: DLX enumerates all 92 solutions in ~1 ms.
# For 18-queens: DLX counts 666 million solutions in ~1 hour.

Practical optimizations

The bare Algorithm X above works correctly but production solvers add tricks:

• Pre-allocated node pool. Use a flat array of node structs indexed by integer rather than allocating objects. Cuts memory allocator overhead to zero during search and improves cache locality 3–5×.
• Constraint propagation before search. Look for naked singles (cells where only one digit fits) and hidden singles (digits that only fit in one cell of a row/column/box). Each pass takes O(n) and can solve easy puzzles entirely without search.
• Watched literals. Borrowed from SAT solvers. Each row maintains two "watched" columns; when one becomes unsatisfiable, only that row needs re-checking. Reduces constant factor by 2–3× on large instances.
• Parallel search. Split the candidate rows of the first chosen column across threads. Each thread runs Algorithm X independently. Near-linear speedup since branches don't share state.
• Algorithm C (colored). Knuth's generalization for "this constraint can be matched in this color" — adds an extra check that nodes can only cover same-colored neighbors. Used for problems like Latin squares with extra constraints.

What can be reduced to exact cover

If you can write your problem as "pick items so each requirement is met exactly once," you can solve it with Algorithm X. Examples:

Problem	Candidate row	Constraint columns
Sudoku (n×n)	Place digit d at (r, c)	cell-filled, row-d, col-d, box-d
N-queens	Queen at (r, c)	row, column, \-diagonal, /-diagonal
Pentomino tiling	Place pentomino P at position (r, c) in orientation o	each square of P, plus "P used"
Soma cube	Place piece P in orientation o at position (x,y,z)	each unit cube of P, plus "P used"
Latin square completion	Place value v at (r, c)	cell-filled, row-v, col-v
Set cover (forced exact)	Pick subset S	each element to be covered
Vertex cover (small k)	Pick vertex v	each edge to be covered (need k or fewer vertices)

The "candidate row × constraint column" formulation is the universal entry point. Once you write it down, DLX does the rest.

Common bugs and edge cases

• Forgetting MRV. Algorithm X works correctly without choosing the smallest column — just slowly. A 9×9 Sudoku without MRV might take seconds; with MRV it takes milliseconds. Always implement the heuristic.
• Failing to stop at first solution. Algorithm X enumerates all solutions by default. If you only need one (typical for Sudoku), have your callback return true to short-circuit; otherwise you'll explore the rest of the tree needlessly.
• Encoding mistakes. Off-by-one in constraint indexing produces nonsensical solutions. Print the matrix with row/column names and spot-check by hand for a tiny instance before scaling up.
• Givens not pre-locked. Sudoku puzzles with givens should restrict candidate rows to only the given digit at that cell — including all 9 candidate rows lets DLX "re-discover" the given, wasting search effort and risking inconsistent puzzles producing wrong solutions.
• Recursive depth on hard instances. Some pentomino tilings require recursion depth > 30; pure-recursive Python hits the default stack limit. Use sys.setrecursionlimit or convert to an iterative form.
• Solution decoding. The output is a list of rowId integers. You must translate back to the original problem domain (cell + digit, queen position, pentomino placement). Keep a rowMeta array alongside the DLX rows for this.