Exact Cover & Knuth's Algorithm X with Dancing Links (DLX)

1. The Exact Cover Problem & Knuth's Algorithm X

Given a universe of constraints $C$ (columns) and a collection of candidate options $R$ (rows), where each row $r \in R$ is a subset of $C$ represented as a $0/1$ matrix $A$, the Exact Cover Problem asks for a subset of rows $R^* \subseteq R$ such that every column $c \in C$ is covered by exactly one row in $R^*$. Exact Cover is NP-complete (Karp, 1972), yet countless constraint satisfaction problems—Sudoku, $N$-Queens, Pentomino tiling, Latin squares—reduce directly to Exact Cover:

• Sudoku as Exact Cover ($729 \text{ rows} \times 324 \text{ columns}$): Each candidate placement $(r, c, d) \in \{0..8\}^3$ is a row (total $9^3 = 729$ rows). Each row has exactly 4 ones across 324 columns:
  1. Cell constraint (81 cols): Cell $(r, c)$ contains a digit.
  2. Row-digit constraint (81 cols): Row $r$ contains digit $d$.
  3. Column-digit constraint (81 cols): Column $c$ contains digit $d$.
  4. Box-digit constraint (81 cols): Box $b(r, c)$ contains digit $d$.

Knuth's Algorithm X solves Exact Cover recursively: If matrix $A$ has no columns left, report the current solution. Otherwise, deterministically choose a column $c$ with the minimum number of 1s (the S-heuristic / MRV). Nondeterministically choose a row $r$ such that $A[r, c] = 1$, add $r$ to the partial solution, and for every column $j$ where $A[r, j] = 1$, delete column $j$ and delete every row $i$ that also has $A[i, j] = 1$ (since $i$ conflicts with $r$ on column $j$). Recurse, then restore everything.

2. Toroidal 2D Doubly Linked Matrix Representation

Only the $1$-entries of $A$ are represented as nodes. Every node $x$ has four pointers (L, R, U, D) and a pointer/index C to its column header. Each column header also tracks S[c], the current number of active 1s in column $c$, and is linked horizontally into a master header list rooted at head.

3. Complexity Matrix

4. Reference C++20 Implementation

#include <cstdint>
#include <limits>
#include <vector>

class DancingLinksSolver {
    struct Node {
        int L, R, U, D, col, row_id;
    };
    std::vector<Node> nodes;
    std::vector<int> col_size;
    std::vector<int> solution;

    void cover(int c) {
        nodes[nodes[c].R].L = nodes[c].L;
        nodes[nodes[c].L].R = nodes[c].R;
        for (int i = nodes[c].D; i != c; i = nodes[i].D) {
            for (int j = nodes[i].R; j != i; j = nodes[j].R) {
                nodes[nodes[j].D].U = nodes[j].U;
                nodes[nodes[j].U].D = nodes[j].D;
                --col_size[nodes[j].col];
            }
        }
    }

    // MUST traverse in exact reverse order (U then L) of cover (D then R)!
    void uncover(int c) {
        for (int i = nodes[c].U; i != c; i = nodes[i].U) {
            for (int j = nodes[i].L; j != i; j = nodes[j].L) {
                ++col_size[nodes[j].col];
                nodes[nodes[j].D].U = j;
                nodes[nodes[j].U].D = j;
            }
        }
        nodes[nodes[c].R].L = c;
        nodes[nodes[c].L].R = c;
    }

public:
    explicit DancingLinksSolver(int num_cols) : nodes(num_cols + 1), col_size(num_cols + 1, 0) {
        for (int c = 0; c <= num_cols; ++c) {
            nodes[c] = { (c == 0 ? num_cols : c - 1), (c == num_cols ? 0 : c + 1), c, c, c, -1 };
        }
    }

    void add_row(int row_id, const std::vector<int>& cols_one_based) {
        int first = -1;
        for (int c : cols_one_based) {
            int idx = static_cast<int>(nodes.size());
            int up = nodes[c].U;
            nodes.push_back({ idx, idx, up, c, c, row_id });
            nodes[up].D = idx;
            nodes[c].U = idx;
            ++col_size[c];
            if (first == -1) {
                first = idx;
            } else {
                int left = nodes[first].L;
                nodes[idx].L = left;
                nodes[idx].R = first;
                nodes[left].R = idx;
                nodes[first].L = idx;
            }
        }
    }

    bool search(std::vector<int>& out_rows) {
        if (nodes[0].R == 0) { // All primary columns covered!
            out_rows = solution;
            return true;
        }
        // S-Heuristic: pick column with minimum remaining 1s
        int best_c = nodes[0].R;
        for (int c = nodes[0].R; c != 0; c = nodes[c].R) {
            if (col_size[c] < col_size[best_c]) best_c = c;
        }
        if (col_size[best_c] == 0) return false; // Dead end: uncovered column has 0 options

        cover(best_c);
        for (int r = nodes[best_c].D; r != best_c; r = nodes[r].D) {
            solution.push_back(nodes[r].row_id);
            for (int j = nodes[r].R; j != r; j = nodes[j].R) {
                cover(nodes[j].col);
            }
            if (search(out_rows)) return true;
            for (int j = nodes[r].L; j != r; j = nodes[j].L) {
                uncover(nodes[j].col);
            }
            solution.pop_back();
        }
        uncover(best_c);
        return false;
    }
};