Build Lab: Knuth's Dancing Links (DLX) Exact Cover & Constraint Satisfaction Solver

1. Primary vs. Secondary Columns in Generalized Exact Cover

Many real-world Constraint Satisfaction Problems (CSPs) combine two types of constraints:

• Primary Constraints (Exact Cover — $\sum_{r \in R^*} A[r, c] = 1$): Every column $c \in [1..N_{\text{primary}}]$ must be covered by the final solution. Example: In $N$-Queens, each of the $N$ rows and $N$ columns must contain exactly one queen. In Sudoku, all $324$ cell/row/col/box constraints are primary.
• Secondary Constraints (At-Most-One — $\sum_{r \in R^*} A[r, c] \le 1$): Each column $c \in [N_{\text{primary}} + 1 .. N_{\text{total}}]$ may be covered at most once. Example: In $N$-Queens, the $2N - 1$ main diagonals and $2N - 1$ anti-diagonals can hold at most one queen (some diagonals remain empty!).

2. End-to-End Sudoku Compiler to 324-Column DLX Torus

For a $9 \times 9$ Sudoku grid, candidate $(r, c, d)$ with $r, c, d \in \{0..8\}$ maps to row ID $81r + 9c + d$ and covers 4 primary columns (1-indexed in $1..324$):

1. $ ext{Col}_{ ext{cell}} = 1 + (9r + c) \in [1..81]$
2. $ ext{Col}_{ ext{row}} = 81 + 1 + (9r + d) \in [82..162]$
3. $ ext{Col}_{ ext{col}} = 162 + 1 + (9c + d) \in [163..243]$
4. $ ext{Col}_{ ext{box}} = 243 + 1 + (9 \cdot (3\lfloor r/3 \rfloor + \lfloor c/3 \rfloor) + d) \in [244..324]$

If cell $(r, c)$ is already pre-filled with clue $d_0$, we emit only the single row $(r, c, d_0)$ instead of all 9 digits $d \in \{0..8\}$. At depth 0 of search(), the S-heuristic sees $S[\text{Col}_{\text{cell}}(r, c)] = 1$ and immediately unit-propagates every pre-filled clue before making a single guess!

3. Complexity Matrix

4. Complete Production C++20 Build Lab Implementation

#include <array>
#include <cstdint>
#include <string>
#include <vector>

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

    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];
            }
        }
    }

    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:
    GeneralizedDLX(int num_primary, int num_secondary = 0, int reserve_nodes = 4096)
        : nodes(num_primary + num_secondary + 1),
          col_size(num_primary + num_secondary + 1, 0) {
        nodes.reserve(reserve_nodes);
        // Link primary columns [1..num_primary] into master header 0
        for (int c = 0; c <= num_primary; ++c) {
            nodes[c] = { (c == 0 ? num_primary : c - 1),
                         (c == num_primary ? 0 : c + 1),
                         c, c, c, -1 };
        }
        // Secondary columns [num_primary+1 .. total] are self-looped horizontally!
        for (int c = num_primary + 1; c <= num_primary + num_secondary; ++c) {
            nodes[c] = { c, c, c, c, c, -1 };
        }
    }

    void add_row(int row_id, const std::vector<int>& cols) {
        int first = -1;
        for (int c : cols) {
            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 solve_one(std::vector<int>& out_solution) {
        if (nodes[0].R == 0) {
            out_solution = partial_sol;
            return true;
        }
        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] <= 1) break; // Early exit if 0 (dead) or 1 (forced unit)
            }
        }
        if (col_size[best_c] == 0) return false;

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

// Complete 9x9 Sudoku Solver compiled to 324-Column Exact Cover
bool solve_sudoku_dlx(std::array<std::string, 9>& board) {
    GeneralizedDLX dlx(324, 0, 3250);
    for (int r = 0; r < 9; ++r) {
        for (int c = 0; c < 9; ++c) {
            int box = (r / 3) * 3 + (c / 3);
            for (int d = 0; d < 9; ++d) {
                if (board[r][c] != '.' && board[r][c] != ('1' + d)) continue;
                int row_id = r * 81 + c * 9 + d;
                int col_cell = 1 + (r * 9 + c);
                int col_row  = 81 + 1 + (r * 9 + d);
                int col_col  = 162 + 1 + (c * 9 + d);
                int col_box  = 243 + 1 + (box * 9 + d);
                dlx.add_row(row_id, { col_cell, col_row, col_col, col_box });
            }
        }
    }
    std::vector<int> sol;
    if (!dlx.solve_one(sol)) return false;
    for (int row_id : sol) {
        int r = row_id / 81;
        int c = (row_id / 9) % 9;
        int d = row_id % 9;
        board[r][c] = static_cast<char>('1' + d);
    }
    return true;
}