Exact Cover

Why Exact Cover Matters

Suppose a puzzle board must be tiled with a fixed collection of pieces. Every board cell must be occupied once, and every piece must be used once. A proposed placement satisfies several requirements together: it uses one piece and occupies several cells. Choosing placements independently can create overlaps or leave gaps. Exact cover makes both mistakes visible in one model: give each requirement a column, give each legal placement a row, and select rows that put exactly one selected entry in every column.

The same representation works for Sudoku candidates, small assignment puzzles, and other systems of discrete choices with exact-once requirements. It extends the choose, recurse, undo pattern from recursion and constraint search: a choice removes the requirements it satisfies and excludes every incompatible choice. A remaining requirement with no candidate proves that the current branch cannot work.

Algorithm X is the search procedure. Dancing Links, usually abbreviated DLX, is a sparse, reversible representation that makes the procedure practical. This lesson develops the exact-once model, traces an unsuccessful branch followed by a successful one, implements indexed DLX in three languages, and explains both its restoration invariant and its exponential worst case.

Core Concepts and Terminology

Let the universe be $U=\{0,1,\ldots,m-1\}$ and let the input have $n$ labeled, nonempty subsets $R_0,\ldots,R_{n-1}\subseteq U$. A solution is a set of row IDs $I$ such that

$$\bigcup_{i\in I}R_i=U,\qquad R_i\cap R_j=\varnothing\quad\text{for distinct }i,j\in I.$$

Equivalently, with incidence matrix $A\in\{0,1\}^{n\times m}$, choose binary variables $x_i$ satisfying

$$\sum_{i=0}^{n-1}A_{i,c}x_i=1\qquad\text{for every }c\in U.$$

The right-hand side is exactly one. Ordinary set cover permits overlapping selected sets; set packing permits requirements to remain uncovered. Neither is the same problem. Exact cover asks for a feasible selection, without automatically minimizing its size or assigning it a cost.

The programs count all solutions and retain the first solution in deterministic search order. Different row IDs remain different choices even if their subsets are identical. Empty candidate rows are rejected, so the algorithm never silently omits optional empty-row selections. An empty universe with no rows has exactly one solution, the empty selection. A nonempty universe with no rows has none.

A node in the search tree is a recursive call with a particular partial selection. At that boundary, the active columns are exactly the requirements not yet satisfied; their active candidate rows are precisely those compatible with the selection. Choose the column with the fewest active candidates, breaking ties by increasing column ID. Visit its candidate rows in increasing input row ID.

Here is the concrete instance used throughout. Its six rows contain $z=17$ total incidences:

• Row 0: $\{0,3,6\}$.
• Row 1: $\{0,3\}$.
• Row 2: $\{3,4,6\}$.
• Row 3: $\{2,4,5\}$.
• Row 4: $\{1,2,5,6\}$.
• Row 5: $\{1,6\}$.

How Exact Cover Works, Step by Step

At each recursive entry, increment the explored-node counter. If the root has no active column header, record the selected row IDs as one complete solution and return. This is a test for no remaining columns, not for no remaining candidate rows. Otherwise scan the active headers for a minimum-size column $c$. If $S[c]=0$, return without modifying the structure: the corresponding requirement cannot be satisfied in this branch.

For a nonempty chosen column, execute these operations in order:

1. Cover $c$ once for the entire candidate loop. Detach its header from the root ring. For each node $i$ down column $c$, traverse the other nodes $j$ in its row rightward and detach each $j$ from its vertical column list. Decrement the appropriate size. The column-$c$ list itself remains available for iterating its candidates.
2. Select a candidate row. Append its original row ID to the explicit selection stack. Traverse its other nodes rightward, covering each associated column. This removes the remaining requirements satisfied by that row and excludes rows that would overlap it.
3. Recurse on the reduced instance. At this boundary the active matrix represents exactly the remaining compatible choices. A solution increments the total but does not end enumeration.
4. Undo this row before advancing. Traverse the selected row leftward and uncover its other columns. Pop its row ID. The reduced state for the next candidate must be exactly the same as before this candidate.
5. After all candidates, uncover $c$. This restores the caller's complete state. Even a successful branch is fully unwound.

The critical local operation uses the detached node's unchanged neighbor indices. Removing a vertical node $j$ assigns D[U[j]] = D[j] and U[D[j]] = U[j]. Restoring it assigns D[U[j]] = j and U[D[j]] = j. Its own U[j] and D[j] were never cleared. Uncover scans column rows upward, and visits their row nodes leftward, before relinking the header.

Covering the branch column is bookkeeping, not a selected-row decision: it removes all its candidate rows from the other lists before the program chooses which one to take. That is why you must not cover the branch column again when traversing the selected row. Each row traversal starts at the node after the node already in that column and stops upon returning to it.

The diagram labels columns using input IDs. In code, root is index 0, input column $c$ has header index $c+1$, and incidence nodes start at index $m+1$. These are integer indices into arrays, with no raw pointers and no node allocation during search. Header order and row rings remain stable under undo, making tie breaking repeatable.

flowchart TD
    A["Enter search; increment nodes"] --> B{"No active columns?"}
    B -->|Yes| C["Count solution; save first; return"]
    B -->|No| D["Choose smallest active column c"]
    D --> E{"Size of c is zero?"}
    E -->|Yes| F["Dead end; return"]
    E -->|No| G["Cover c once"]
    G --> H{"Another candidate row in c?"}
    H -->|Yes| I["Push row; cover its other columns rightward"]
    I --> J["Recurse on remaining requirements"]
    J --> K["Uncover other columns leftward; pop row"]
    K --> H
    H -->|No| L["Uncover c; return"]

Worked Example with a Full Trace

Use the six-row instance above. The initial candidate lists, in input-column order, are 0:[0,1], 1:[4,5], 2:[3,4], 3:[0,1,2], 4:[2,3], 5:[3,4], 6:[0,2,4,5]. Their sizes are $[2,2,2,3,2,2,4]$. Several columns tie at size two; choose column 0 because it comes first.

Covering column 0 hides its header and unlinks row 0's entries in columns 3 and 6, then row 1's entry in column 3. There have now been one cover and three incidence unlinks. The branch loop still has row IDs 0 and 1 available in column 0.

First candidate, row 0. Push 0, cover column 3, then cover column 6. Cover 3 removes row 2's remaining entries in columns 4 and 6. Cover 6 then removes row 4's entries in columns 1, 2, 5 and row 5's entry in column 1. The next recursive entry has active columns 1, 2, 4, 5 with sizes $[0,1,1,1]$. Column 1 has no candidate, so prune this branch. Uncover 6, uncover 3, and pop row 0. Keep column 0 covered while moving to its next candidate.

Second candidate, row 1. Push 1 and cover its other column, 3. The recursive entry now has columns 1, 2, 4, 5, 6, with sizes $[2,2,1,2,2]$. Column 4 uniquely has minimum size; its only candidate is row 3.

Forced row 3. Cover 4, push row 3, and follow its row ring from column 4: cover 5, then wrap around and cover 2. The active columns are now 1 and 6, both with row 5 as their only candidate. Choose column 1 by the tie rule.

Forced row 5. Cover 1, push row 5, and cover 6. No active columns remain. Record $[1,3,5]$: the subsets $\{0,3\}$, $\{2,4,5\}$, and $\{1,6\}$ are pairwise disjoint and cover $U$.

Every cover call, including calls with no incidence unlink, is listed below. Counters are cumulative, so uncovering never subtracts from them. The chosen column is covered before its row is pushed.

After recording the cover, unwind in this exact order: uncover 6; pop 5; uncover 1; uncover 2 then 5; pop 3; uncover 4; uncover 3; pop 1; uncover 0. The failed branch had already uncovered 6 then 3 and popped 0. No sibling candidates remain in the successful branch. The complete run uses five search entries, nine cover calls, and seventeen incidence unlinks, with one solution. Every structural array and every column size matches its initial value afterward.

Implementation in Python, C++, and Java

Each complete program implements the same indexed DLX search. Inputs use zero-based column IDs and input row IDs. A row may list its columns in any order: construction copies and sorts each row, preserving the caller's data. Arrays and rows must be non-null, and IDs must be integers. Validation rejects negative or out-of-range columns, a repeated column within a row, an empty row, or an input exceeding the demonstration limits.

The limits are twenty columns and twenty candidate rows. They keep recursion shallow and make all solution and instrumentation counters safe in C++ and Java's signed 64-bit types. The algorithm generalizes to larger instances, but raising those limits requires revisiting capacity, counter overflow, and runtime. The later Sudoku encoding discussion describes the model; a full Sudoku matrix exceeds these demonstration limits.

nodes counts recursive entries, including successful leaves and dead ends. covers counts cover calls, including ones with no incidence deletion. unlinks counts only vertical incidence-node removals; it excludes header removal and subsequent restoration. These totals describe implementation work and are not interchangeable with the number of selected rows.

solve() snapshots the structural arrays, resets the result and counters, enumerates all covers, and verifies exact restoration and an empty selection stack. It can be called again on the same constructed object. Only the first solution's row IDs are retained; enumeration does not store every solution. first=[] occurs both for an unsatisfiable instance and for the valid empty cover, so consult the solution count. A copied result survives the next solve.

class DLX:
    LIMIT = 20

    def __init__(self, columns, rows):
        if type(columns) is not int or not 0 <= columns <= self.LIMIT:
            raise ValueError("column count out of range")
        if len(rows) > self.LIMIT:
            raise ValueError("too many rows")
        normalized = []
        for row in rows:
            if not row or any(type(c) is not int or not 0 <= c < columns for c in row):
                raise ValueError("empty row or column out of range")
            if len(set(row)) != len(row):
                raise ValueError("duplicate column within a row")
            normalized.append(sorted(row))
        n = columns + 1 + sum(map(len, normalized))
        self.L = list(range(n))
        self.R = list(range(n))
        self.U = list(range(n))
        self.D = list(range(n))
        self.C = [0] * n
        self.row = [-1] * n
        self.S = [0] * (columns + 1)
        for c in range(columns + 1):
            self.L[c] = c - 1 if c else columns
            self.R[c] = c + 1 if c < columns else 0
            self.C[c] = c
        k = columns + 1
        for rid, cells in enumerate(normalized):
            first = k
            for column in cells:
                c = column + 1
                self.C[k], self.row[k] = c, rid
                self.U[k], self.D[k] = self.U[c], c
                self.D[self.U[c]] = k
                self.U[c] = k
                self.S[c] += 1
                self.L[k] = k - 1 if k > first else k
                self.R[k] = first
                self.R[self.L[k]] = k
                self.L[first] = k
                k += 1
        self.chosen = []
        self.first = []
        self.count = self.nodes = self.covers = self.unlinks = 0

    def state(self):
        return tuple(tuple(a) for a in (self.L, self.R, self.U, self.D,
                                        self.C, self.row, self.S))

    def cover(self, c):
        self.covers += 1
        self.R[self.L[c]] = self.R[c]
        self.L[self.R[c]] = self.L[c]
        i = self.D[c]
        while i != c:
            j = self.R[i]
            while j != i:
                self.D[self.U[j]] = self.D[j]
                self.U[self.D[j]] = self.U[j]
                self.S[self.C[j]] -= 1
                self.unlinks += 1
                j = self.R[j]
            i = self.D[i]

    def uncover(self, c):
        i = self.U[c]
        while i != c:
            j = self.L[i]
            while j != i:
                self.S[self.C[j]] += 1
                self.D[self.U[j]] = j
                self.U[self.D[j]] = j
                j = self.L[j]
            i = self.U[i]
        self.R[self.L[c]] = c
        self.L[self.R[c]] = c

    def search(self):
        self.nodes += 1
        if self.R[0] == 0:
            self.count += 1
            if self.count == 1:
                self.first = self.chosen.copy()
            return
        c = self.R[0]
        h = self.R[c]
        while h != 0:
            if self.S[h] < self.S[c]:
                c = h
            h = self.R[h]
        if self.S[c] == 0:
            return
        self.cover(c)
        r = self.D[c]
        while r != c:
            self.chosen.append(self.row[r])
            j = self.R[r]
            while j != r:
                self.cover(self.C[j])
                j = self.R[j]
            self.search()
            j = self.L[r]
            while j != r:
                self.uncover(self.C[j])
                j = self.L[j]
            self.chosen.pop()
            r = self.D[r]
        self.uncover(c)

    def solve(self):
        before = self.state()
        self.chosen.clear()
        self.first = []
        self.count = self.nodes = self.covers = self.unlinks = 0
        self.search()
        if self.state() != before or self.chosen:
            raise RuntimeError("undo failed")
        return self.count, self.first.copy(), self.nodes, self.covers, self.unlinks


def show(name, columns, rows):
    solver = DLX(columns, rows)
    count, first, nodes, covers, unlinks = solver.solve()
    print(f"{name}: solutions={count}, nodes={nodes}, covers={covers}, unlinks={unlinks}")
    print("first=[" + ",".join(map(str, first)) + "], restored=YES")


def main():
    show("classic", 7, [[0, 3, 6], [0, 3], [3, 4, 6],
                        [2, 4, 5], [1, 2, 5, 6], [1, 6]])
    show("multiple", 3, [[0], [1], [2], [0, 1], [1, 2], [0, 2], [0, 1, 2]])
    show("missing", 2, [[0]])
    show("duplicate rows", 1, [[0], [0]])
    show("empty", 0, [])
    print("checks = PASS")


if __name__ == "__main__":
    main()

#include <algorithm>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <string>
#include <vector>
using namespace std;

struct Result {
    long long count, nodes, covers, unlinks;
    vector<int> first;
};

class DLX {
public:
    static const int LIMIT = 20;
    vector<int> L, R, U, D, C, row, S, chosen, first;
    long long count = 0, nodes = 0, covers = 0, unlinks = 0;

    DLX(int columns, vector<vector<int>> rows) {
        if (columns < 0 || columns > LIMIT || rows.size() > LIMIT)
            throw invalid_argument("input exceeds limits");
        int n = columns + 1;
        for (auto& cells : rows) {
            if (cells.empty()) throw invalid_argument("empty row");
            for (int c : cells)
                if (c < 0 || c >= columns) throw invalid_argument("column out of range");
            sort(cells.begin(), cells.end());
            if (adjacent_find(cells.begin(), cells.end()) != cells.end())
                throw invalid_argument("duplicate column within a row");
            n += static_cast<int>(cells.size());
        }
        L.resize(n); R.resize(n); U.resize(n); D.resize(n);
        iota(L.begin(), L.end(), 0); R = U = D = L;
        C.assign(n, 0); row.assign(n, -1); S.assign(columns + 1, 0);
        for (int c = 0; c <= columns; ++c) {
            L[c] = c ? c - 1 : columns;
            R[c] = c < columns ? c + 1 : 0;
            C[c] = c;
        }
        int k = columns + 1;
        for (int rid = 0; rid < static_cast<int>(rows.size()); ++rid) {
            int start = k;
            for (int column : rows[rid]) {
                int c = column + 1;
                C[k] = c; row[k] = rid;
                U[k] = U[c]; D[k] = c;
                D[U[c]] = k; U[c] = k; ++S[c];
                L[k] = k > start ? k - 1 : k;
                R[k] = start; R[L[k]] = k; L[start] = k;
                ++k;
            }
        }
    }

    vector<vector<int>> state() const {
        return {L, R, U, D, C, row, S};
    }

    void cover(int c) {
        ++covers;
        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]) {
                D[U[j]] = D[j]; U[D[j]] = U[j];
                --S[C[j]]; ++unlinks;
            }
    }

    void uncover(int c) {
        for (int i = U[c]; i != c; i = U[i])
            for (int j = L[i]; j != i; j = L[j]) {
                ++S[C[j]];
                D[U[j]] = j; U[D[j]] = j;
            }
        R[L[c]] = c; L[R[c]] = c;
    }

    void search() {
        ++nodes;
        if (R[0] == 0) {
            ++count;
            if (count == 1) first = chosen;
            return;
        }
        int c = R[0];
        for (int h = R[c]; h != 0; h = R[h])
            if (S[h] < S[c]) c = h;
        if (S[c] == 0) return;
        cover(c);
        for (int r = D[c]; r != c; r = D[r]) {
            chosen.push_back(row[r]);
            for (int j = R[r]; j != r; j = R[j]) cover(C[j]);
            search();
            for (int j = L[r]; j != r; j = L[j]) uncover(C[j]);
            chosen.pop_back();
        }
        uncover(c);
    }

    Result solve() {
        auto before = state();
        chosen.clear(); first.clear();
        count = nodes = covers = unlinks = 0;
        search();
        if (state() != before || !chosen.empty()) throw logic_error("undo failed");
        return {count, nodes, covers, unlinks, first};
    }
};

void show(const string& name, int columns, const vector<vector<int>>& rows) {
    DLX solver(columns, rows);
    auto r = solver.solve();
    cout << name << ": solutions=" << r.count << ", nodes=" << r.nodes
         << ", covers=" << r.covers << ", unlinks=" << r.unlinks << '\n';
    cout << "first=[";
    for (size_t i = 0; i < r.first.size(); ++i) {
        if (i) cout << ',';
        cout << r.first[i];
    }
    cout << "], restored=YES\n";
}

int main() {
    show("classic", 7, { {0, 3, 6}, {0, 3}, {3, 4, 6},
                         {2, 4, 5}, {1, 2, 5, 6}, {1, 6} });
    show("multiple", 3, { {0}, {1}, {2}, {0, 1}, {1, 2}, {0, 2}, {0, 1, 2} });
    show("missing", 2, { {0} });
    show("duplicate rows", 1, { {0}, {0} });
    show("empty", 0, {});
    cout << "checks = PASS\n";
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static final class Result {
        long count, nodes, covers, unlinks;
        List<Integer> first;
        Result(long count, long nodes, long covers, long unlinks, List<Integer> first) {
            this.count = count; this.nodes = nodes;
            this.covers = covers; this.unlinks = unlinks;
            this.first = new ArrayList<>(first);
        }
    }

    static final class DLX {
        static final int LIMIT = 20;
        int[] L, R, U, D, C, row, S;
        List<Integer> chosen = new ArrayList<>(), first = new ArrayList<>();
        long count, nodes, covers, unlinks;

        DLX(int columns, int[][] input) {
            if (columns < 0 || columns > LIMIT || input.length > LIMIT)
                throw new IllegalArgumentException("input exceeds limits");
            int[][] rows = new int[input.length][];
            int n = columns + 1;
            for (int i = 0; i < input.length; ++i) {
                rows[i] = input[i].clone();
                if (rows[i].length == 0) throw new IllegalArgumentException("empty row");
                for (int c : rows[i])
                    if (c < 0 || c >= columns)
                        throw new IllegalArgumentException("column out of range");
                Arrays.sort(rows[i]);
                for (int j = 1; j < rows[i].length; ++j)
                    if (rows[i][j] == rows[i][j - 1])
                        throw new IllegalArgumentException("duplicate column within a row");
                n += rows[i].length;
            }
            L = new int[n]; R = new int[n]; U = new int[n]; D = new int[n];
            C = new int[n]; row = new int[n]; S = new int[columns + 1];
            Arrays.fill(row, -1);
            for (int k = 0; k < n; ++k) L[k] = R[k] = U[k] = D[k] = k;
            for (int c = 0; c <= columns; ++c) {
                L[c] = c == 0 ? columns : c - 1;
                R[c] = c < columns ? c + 1 : 0;
                C[c] = c;
            }
            int k = columns + 1;
            for (int rid = 0; rid < rows.length; ++rid) {
                int start = k;
                for (int column : rows[rid]) {
                    int c = column + 1;
                    C[k] = c; row[k] = rid;
                    U[k] = U[c]; D[k] = c;
                    D[U[c]] = k; U[c] = k; ++S[c];
                    L[k] = k > start ? k - 1 : k;
                    R[k] = start; R[L[k]] = k; L[start] = k;
                    ++k;
                }
            }
        }

        int[][] state() {
            return new int[][] { L.clone(), R.clone(), U.clone(), D.clone(),
                                 C.clone(), row.clone(), S.clone() };
        }

        void cover(int c) {
            ++covers;
            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]) {
                    D[U[j]] = D[j]; U[D[j]] = U[j];
                    --S[C[j]]; ++unlinks;
                }
        }

        void uncover(int c) {
            for (int i = U[c]; i != c; i = U[i])
                for (int j = L[i]; j != i; j = L[j]) {
                    ++S[C[j]];
                    D[U[j]] = j; U[D[j]] = j;
                }
            R[L[c]] = c; L[R[c]] = c;
        }

        void search() {
            ++nodes;
            if (R[0] == 0) {
                ++count;
                if (count == 1) first = new ArrayList<>(chosen);
                return;
            }
            int c = R[0];
            for (int h = R[c]; h != 0; h = R[h])
                if (S[h] < S[c]) c = h;
            if (S[c] == 0) return;
            cover(c);
            for (int r = D[c]; r != c; r = D[r]) {
                chosen.add(row[r]);
                for (int j = R[r]; j != r; j = R[j]) cover(C[j]);
                search();
                for (int j = L[r]; j != r; j = L[j]) uncover(C[j]);
                chosen.remove(chosen.size() - 1);
            }
            uncover(c);
        }

        Result solve() {
            int[][] before = state();
            chosen.clear(); first.clear();
            count = nodes = covers = unlinks = 0;
            search();
            if (!Arrays.deepEquals(state(), before) || !chosen.isEmpty())
                throw new IllegalStateException("undo failed");
            return new Result(count, nodes, covers, unlinks, first);
        }
    }

    static void show(String name, int columns, int[][] rows) {
        DLX solver = new DLX(columns, rows);
        Result r = solver.solve();
        System.out.println(name + ": solutions=" + r.count + ", nodes=" + r.nodes
                + ", covers=" + r.covers + ", unlinks=" + r.unlinks);
        StringBuilder out = new StringBuilder("first=[");
        for (int i = 0; i < r.first.size(); ++i) {
            if (i != 0) out.append(',');
            out.append(r.first.get(i));
        }
        System.out.println(out + "], restored=YES");
    }

    public static void main(String[] args) {
        show("classic", 7, new int[][] { {0, 3, 6}, {0, 3}, {3, 4, 6},
                                       {2, 4, 5}, {1, 2, 5, 6}, {1, 6} });
        show("multiple", 3, new int[][] { {0}, {1}, {2}, {0, 1}, {1, 2}, {0, 2}, {0, 1, 2} });
        show("missing", 2, new int[][] { {0} });
        show("duplicate rows", 1, new int[][] { {0}, {0} });
        show("empty", 0, new int[][] {});
        System.out.println("checks = PASS");
    }
}

Expected stdout, identical in all three languages:

• classic: solutions=1, nodes=5, covers=9, unlinks=17
• first=[1,3,5], restored=YES
• multiple: solutions=5, nodes=10, covers=10, unlinks=8
• first=[0,1,2], restored=YES
• missing: solutions=0, nodes=1, covers=0, unlinks=0
• first=[], restored=YES
• duplicate rows: solutions=2, nodes=3, covers=1, unlinks=0
• first=[0], restored=YES
• empty: solutions=1, nodes=1, covers=0, unlinks=0
• first=[], restored=YES
• checks = PASS

For multiple, the five covers are $\{0,1,2\}$, $\{0,4\}$, $\{3,2\}$, $\{5,1\}$, and $\{6\}$ as sets of row IDs. For duplicate rows, either of the two labeled rows alone covers column 0, hence two solutions. Selecting both is invalid.

The implementations were compared on 9,559 cases per language: exhaustive ordered row sequences of lengths zero through four over all seven nonempty subsets of a three-element universe; every family of at most five distinct nonempty subsets of a four-element universe; 1,800 seeded random instances; boundary fixtures; and eight invalid inputs. Of the valid cases, 6,527 were satisfiable and 3,024 were not. An independent include/exclude subset oracle verified counts, and an immutable Algorithm X model verified the first solution and all counters. Column order was shuffled within input rows, including 20,446 unsorted rows; normalization preserved results and caller data. Repeated solves produced identical results without changing inputs. Instrumented Python also checked every current column-list size and neighbor relation, and 86,836 individual cover/uncover pairs restored their exact saved arrays. C++ ran with address and undefined-behavior sanitizers; Java ran with assertions enabled.

Complexity, Correctness, and Invariants

Let $m$ be the number of columns, $n$ the number of nonempty candidate rows, $z=\sum_i\lvert R_i\rvert$ the incidence count, $h\le\min(m,n)$ the maximum selection depth, and $N$ the number of recursive entries. Discuss these parameters without the programs' fixed demonstration limits; otherwise every accepted input would have a constant-size bound.

Construction takes $O(m+n+z+\sum_i\lvert R_i\rvert\log(\max(2,\lvert R_i\rvert)))$ time because the code validates and sorts each row. For already validated, sorted rows, building the links is $O(m+n+z)$. Snapshot creation and final comparison take $O(m+z)$ time and space. The input model has no empty rows, so $n\le z$ whenever there are rows.

At a search entry, choosing the minimum column scans at most $m$ headers. A single pointer unlink is constant time, but covering a column is not: it visits all affected row nodes. Along one branch transition, covering the chosen row's columns removes at most $z$ incidence nodes and visits at most $O(m+z)$ list elements. Charge that transition to its child entry, and charge the initial branch-column cover to its parent. Reverse restoration has the same order of work. Thus a conservative whole-search bound is

$$T_{\text{search}}=O\bigl(N(m+z+1)\bigr).$$

No two paths can reach the same compatible set of chosen row IDs: their first differing choices would be two rows covering the same branch column, which cannot both belong to that set. Therefore $N\le 2^n$, giving the conservative worst-case bound $O(2^n(m+z+1))$, plus construction. Some families have exponentially many solutions, so enumerating all of them necessarily takes exponential time. Minimum-column branching is a useful heuristic, not a polynomial-time guarantee.

The best terminal search is $O(1)$ for the empty universe. A nonempty instance with a zero-size column at its root returns after an $O(m)$ header scan; construction still processes the input. There is no distribution-independent average-case bound: sparsity, row overlap, and heuristic choices determine the search tree. A sequence of forced choices also incurs repeated header scans, even though it has no branching.

All DLX arrays, the verification snapshot, the selection stack, and the saved first solution together use $O(m+n+z+h)$ space, which simplifies to $O(m+z)$ under this nonempty-row model. The algorithm stores the search path, not the whole search tree or all solutions. Returning every cover would add space proportional to the total output size.

For the mask DP, begin with one way to cover mask zero. Process each labeled row once, either skipping it or adding it only to masks disjoint from its own mask. Accumulate counts for the union masks; the full-universe mask is the answer. This is different from a recurrence that freely appends rows in arbitrary order, which would count permutations of the same cover. Large counts require adequate integer precision in both approaches.

Correctness follows by induction on the recursive calls. At entry, selected rows are pairwise disjoint, and active columns are precisely those outside their union. For any selected active column $c$, every valid completion must contain exactly one of its current candidate rows. The candidate loop explores all such possibilities; choosing one excludes exactly its overlapping rows and removes exactly its satisfied requirements. A zero-size active column rules out every completion. An empty header ring certifies that all requirements have been covered once. The branches are disjoint because distinct candidates for $c$ cannot coexist in a cover. Exact undo restores the caller's state, so an earlier branch cannot corrupt or suppress a later one.

Variants, Pitfalls, and Optimizations

First solution or bounded enumeration. Returning after one cover can save substantial time, but an early-exit signal must propagate only after each active frame uncovers its selected row's other columns, pops the row, and uncovers the branch column. A search stopped after two solutions proves non-uniqueness; a count of one at that stopping point proves uniqueness only if enumeration actually completed. The supplied programs enumerate fully and have no early-exit mode.

Primary and secondary columns. Generalized exact cover distinguishes requirements that must be covered exactly once from optional constraints that may be covered at most once. Only primary headers belong in the root's branching ring; secondary columns still remove conflicts when selected. This models queens with board rows and board columns as primary constraints and diagonals as secondary constraints. Requiring every diagonal to be covered would encode a different, usually impossible problem. The supplied code treats every column as primary; it does not implement this extension.

Modeling and symmetry. For a tiling, use a column for every board cell and another for every labeled piece; otherwise the search may reuse a piece or omit one. Identical interchangeable pieces and board rotations can produce equivalent geometric answers represented by different row-ID covers. Define the intended notion of distinctness before adding symmetry breaking. Any symmetry restriction needs an argument that it retains a representative of every solution class.

Heuristics and instrumentation. Minimum column size implements the most-constrained requirement rule, using sizes maintained during updates. Ties and candidate ordering affect the first solution and the tree shape. Trying likely rows first can help when stopping at one solution; it does not by itself eliminate solutions when counting all. Degree heuristics, symmetry constraints, and preselected givens may reduce the tree, while array layout and avoiding allocation reduce per-node cost. Measure nodes as well as pointer work: two searches can explore similar trees with different update costs.

The common implementation failure is restoration in the same order as deletion. A detached node remembers the neighbors it had at deletion time, and those neighbors may themselves have been detached later. Reinstall the later changes first.

For live nodes, neighbor reciprocity must hold and the recorded size must equal the number reachable from the header. Detached nodes deliberately retain stale neighbors, so assertions that demand reciprocity from every allocated node during search are incorrect. Compare complete arrays only across a matched cover/uncover boundary or before and after the whole solve. Never clear a detached node's neighbor fields as a cleanup step.

Do not confuse a zero-size column with success, or read S as a permanent input degree. Covering updates sizes even for headers that may currently be hidden; reversing the updates matters when those headers return. Do not cover the branch column twice, advance a candidate iterator before undo, or return a reference to the mutable selection stack as the saved answer.

Practice Problems and Real-World Use

Start with a tiny universe and enumerate all row subsets as an oracle before optimizing. Check that every returned selection has coverage count exactly one in every column, then compare full solution counts. Include missing requirements, repeated labeled rows, unsorted row entries, invalid repeated columns within one row, the empty universe, and an instance whose first branch fails. Reuse the same solver object to catch incomplete restoration.

A standard $9\times9$ Sudoku encoding has $729$ possible candidate rows, one for each cell-digit choice, and $324$ primary columns: $81$ cell requirements, $81$ row-digit requirements, $81$ column-digit requirements, and $81$ box-digit requirements. Every candidate row has four incidences. Filter incompatible candidates for clues or preselect their rows using a carefully reversible operation. An individual candidate is a row of the incidence matrix, not an entire Sudoku row. These dimensions describe the unrestricted encoding before clues and exceed the example programs' size limits.

For applications with preferences or varying costs, exact-cover feasibility may be only part of the model. Consider binary integer optimization when the objective and side constraints dominate; consider a general constraint solver when propagation across richer variable domains matters. DLX is particularly natural when a sparse set of exact-once requirements already expresses the problem cleanly.

For the original presentation, see Donald Knuth's Dancing Links, which develops Algorithm X, reversible linked updates, minimum-column branching, and generalized exact cover. The indexed programs and the detailed counter trace here are a separate teaching implementation. The distinction to retain is the one between search choices and state representation: Algorithm X organizes the alternatives, while DLX makes changing and restoring the sparse state efficient.