xli. Sudoku

Problem. Fill an $N\times N$ grid ($N=B^2$, classic $B=3$) with digits $\mathrm{1..}N$ so that every row, column and $B\times B$ box contains each digit once, extending the given clues.

View	Formulation	Use
backtracking with bitmasks	per row / column / box a mask of used digits; candidates = complement of the union	fastest simple solver
constraint propagation	naked single: a cell with one candidate; hidden single: a digit with one possible cell in a unit	what MRV does implicitly; humans solve with it
exact cover	$N^3$ rows (cell, digit), $4N^2$ columns: cell filled, row has digit, column has digit, box has digit	Dancing Links, see Exact Cover and Dancing Links
graph colouring	the Sudoku graph ($N^2$ vertices, each adjacent to $3N-2B-1$ others: 20 for $N=9$)	proper $N$-colouring extending a precolouring
complexity	$N^2\times N^2$ Sudoku completion is NP-complete (Yato and Seta, 2003)	no polynomial algorithm expected

Count	Value
completed $4\times 4$ grids (Shidoku)	288
completed $9\times 9$ grids	$6670903752021072936960$ (Felgenhauer and Jarvis, 2005)
essentially different $9\times 9$ grids (up to symmetry and relabelling)	$5472730538$ (Russell and Jarvis, 2006)
minimum clues for a unique solution	17 (McGuire, Tugemann and Civario 2012, exhaustive computer search)

// N x N Sudoku, N = B * B; g[r][c] = 0 for empty, else 1..N. Counts solutions up to `limit`
// (limit = 1: solve, limit = 2: uniqueness check); the first solution found is stored in sol.
struct Sudoku {
    int B, N, full; vector<vector<int>> g, sol; vector<int> row, col, box; ll found = 0, limit = 1; bool ok = true;
    Sudoku(int B, const vector<vector<int>>& g0) : B(B), N(B * B), full((1 << B * B) - 1), g(g0), row(N), col(N), box(N) {
        for (int r = 0; r < N; r++) for (int c = 0; c < N; c++) if (int d = g[r][c]) {
            int bit = 1 << (d - 1), b = r / B * B + c / B;
            if ((row[r] | col[c] | box[b]) & bit) ok = false;   // contradictory clues
            row[r] |= bit; col[c] |= bit; box[b] |= bit;
        }
    }
    void dfs() {
        int br = -1, bc = -1, best = N + 1, cand = 0;
        for (int r = 0; r < N; r++) for (int c = 0; c < N; c++) if (!g[r][c]) {   // minimum remaining values
            int m = full & ~(row[r] | col[c] | box[r / B * B + c / B]), k = __builtin_popcount(m);
            if (k < best) { best = k, br = r, bc = c, cand = m; if (k == 0) return; }
        }
        if (br < 0) { if (found++ == 0) sol = g; return; }
        int b = br / B * B + bc / B;
        for (int m = cand; m && found < limit; m &= m - 1) {
            int bit = m & -m;
            g[br][bc] = __builtin_ctz(bit) + 1; row[br] ^= bit; col[bc] ^= bit; box[b] ^= bit;
            dfs();
            g[br][bc] = 0; row[br] ^= bit; col[bc] ^= bit; box[b] ^= bit;
        }
    }
    ll count(ll lim) { limit = lim; found = 0; if (ok) dfs(); return found; }
};

Proof: the solver is complete, and the Shidoku count

Every completion assigns a digit to the chosen cell, and that digit must be absent from the cell’s row, column and box, i.e. in cand. So branching on all candidates of one empty cell partitions the completions of the current grid; recursing, every completion is reached exactly once, and only valid grids are reached because each placement respects the masks. The choice of cell does not affect correctness, only speed: choosing the cell with the fewest candidates (MRV) makes forced cells (naked singles) cost no branching, and a cell with zero candidates proves the branch dead immediately. With limit = 2 the search stops as soon as a second solution exists, which is the uniqueness test used to set puzzles.

Exact cover. Choosing (cell, digit) pairs so that each of the $4N^2$ constraints “cell $(r,c)$ is filled”, “row $r$ contains $d$”, “column $c$ contains $d$”, “box $b$ contains $d$” is satisfied exactly once is the same as a valid completed grid: the first family gives one digit per cell, the others forbid repeats, and counting ($N^2$ cells, $N$ digits per unit) shows no constraint can be missed.

Shidoku. Relabel digits so the top-left box is $\begin{array}{cc}1& 2\\ 3& 4\end{array}$ ($4!=24$ choices); the search then finds 12 completions, so there are $24\cdot 12=288$ grids, matching count on the empty $4\times 4$ grid. Checked against a naive row-major backtracking counter on random $4\times 4$ puzzles, and on $9\times 9$ puzzles (including “the world’s hardest Sudoku” by Inkala) by validating the solution and its uniqueness. The $9\times 9$ counts and the 17-clue bound in the table are results of large computer searches, quoted.

Related notes

• Exact Cover and Dancing Links
• Backtracking and Pruning
• Graph Coloring
• Latin Squares (a solved Sudoku is a Latin square)