2023–2024 · completed

Counting and solving Sudoku

How many Sudoku grids exist, and can a grid be solved by projecting onto convex sets instead of searching? The counts come from the literature; the TIPE reproduced and explained them, then tested the solver.

TIPE research project, preparatory classes, Lycée Sainte-Geneviève.

Fig. 1 Pick a grid or type one, then run a solver in your browser. Alternating projections on the convex relaxation solve the 30-clue grid but stall on harder ones. Douglas–Rachford projects onto the exact constraints (one digit per cell, row, column and box) and solves all three, the 17-clue grid included, in a few hundred iterations.

complete grids (Felgenhauer & Jarvis, 2005): 6.67 × 10²¹
essentially different grids (Russell & Jarvis, 2006, Burnside’s lemma): 5,472,730,538
minimum clues for a unique solution (McGuire et al., 2012): 17

How it works

Fig. 2 The three solvers. Left: alternating projections bounce between two convex sets, the rules and the cube, and slow down or stall where the sets meet in fractional points. Middle: Douglas–Rachford uses the exact, non-convex set of one-hot vectors: it reflects through it, then through the set where its four copies agree, and averages with where it started, which lets it leave traps. Right: backtracking fills the cell with the fewest candidates, and undoes the last choice when a cell has none left.

A grid is a binary vector of 729 entries and the rules are 324 linear equations A·v = 1. The first solver alternates projections between that affine set (via the pseudo-inverse of A) and the cube [0,1]⁷²⁹; it only works when this convex relaxation is tight. The second, Douglas–Rachford, averages reflections through the exact constraints instead: every cell, row, column and box holds exactly one of each digit, a projection that keeps the largest value of each group of nine.

Results

alternating projectionsDouglas–Rachfordbacktracking

Fig. 3 Solve time per grid on the 132 TIPE grids, measured with this page’s solvers in Node (log scale). Alternating projections solve every easy and intermediate grid but none of the 17-clue ones within 20,000 iterations (top line). Douglas–Rachford solves all of them, the 17-clue grids in about 100 ms; backtracking with the fewest-candidates rule solves all of them in under 0.2 s.

Fig. 4 Median number of steps per grid on the TIPE grids, log scale, with the share of grids solved (projections capped at 20,000 iterations, naive backtracking at 20 million nodes, unsolved grids counted at the cap). Steps are not comparable in cost: an alternating-projection iteration multiplies a 729 × 324 matrix by a vector, about 236,000 multiply-adds; a Douglas–Rachford iteration only averages four copies and keeps the largest of each group of nine, about 15,000 operations; a backtracking node checks about twenty cells.

Alternating projections on the convex relaxation solve all 100 easy and intermediate grids but none of the 32 grids with 17 clues. Douglas–Rachford on the exact constraints solves all 132, the 17-clue grids in a median of 970 iterations, about 100 ms, still a projection method but no longer a convex one. Backtracking that picks the most constrained cell remains the fastest.

Technical details

Encoding

A grid becomes a vector v ∈ {0,1}⁷²⁹, one coordinate per (cell, digit) pair, at index 81·row + 9·column + digit. The rules are 324 linear equations A v = 1 in four blocks of 81 rows: each cell holds one digit, each row, column and box holds each digit once. A has rank 249, so its pseudo-inverse is computed from an SVD with a relative cutoff.

Unknowns: 729 binary variables
Rule matrix A: 324 × 729, rank 249
Affine projection: x ↦ x − A⁺(A x − 1)
Box projection: clip to [0,1], given cells pinned
Stopping: rounded grid valid, or 20,000 iterations
Douglas–Rachford: 4 copies (cells, rows, columns, boxes), reflect through each, average; each projection keeps the largest of 9

The three solvers, step by step

1. Alternating projections. Start from any vector. Project it onto the affine set A v = 1 (the closest vector that satisfies all 324 rules, computed once with the pseudo-inverse of A), then onto the cube [0,1]⁷²⁹ (clip every coordinate to [0,1], pin the given cells), and repeat. Both sets are convex, so the iterates converge to a point of their intersection. On easy grids that intersection is the solution alone. On hard ones it also contains fractional points, a cell that is half a 3 and half a 7, and the iterates stall there.

2. Douglas–Rachford. Keep four copies of the vector, one per family of rules (cells, rows, columns, boxes). The set of allowed values is now exact and not convex: in every group of nine, one coordinate is 1 and the others 0, so projecting just keeps the largest value of each group. One step reflects each copy through that set (go to the projection, then as far again), reflects the result through the set where the four copies agree (their average), and moves halfway between the start and that double reflection. Fractional points are no longer allowed, and the reflections keep the iterates from settling in a wrong corner.

3. Backtracking. Pick the empty cell with the fewest possible digits, try each one in turn, and continue; when some cell has no possible digit left, undo the last choice. It is an exact search, and choosing the most constrained cell first keeps the tree small.

Solvers compared

The TIPE compared four solvers: alternating projections, the same with naked-single propagation after each step (every cell left with one candidate is filled), naive backtracking (first empty cell, digits 1 to 9) and backtracking that branches on the cell with the fewest candidates. Simulated annealing was also coded (energy = violated constraints, T₀ = 50,000, cooling 0.999) but left out of the final results.

The figures on this page come from a 2026 re-run of the same methods in TypeScript, on the TIPE's 50 easy, 50 intermediate and 32 seventeen-clue grids, plus Douglas–Rachford, added in 2026 after Elser and after Aragón Artacho, Borwein and Tam (2014), which fixes the projections' failure on hard grids. In the 2024 Python runs on 7 seventeen-clue grids, read from the defence charts, the improved projection solved 2 of them, in roughly 1,500 and 10,000 s, and the improved backtracking all 7, in roughly 100 to 3,000 s.

Cost of one projection step: ≈ 236,000 multiply-adds (729 × 324 matrix)
Cost of one backtracking node: ≈ 20 cell checks
Projections, easy / intermediate: 25 / 200 iterations (median), 100% solved
Projections, 17 clues: 0 of 32 within 20,000 iterations
Douglas–Rachford, 17 clues: 32 of 32, median 970 iterations (≈ 100 ms)
Naive backtracking, 17 clues: 20 of 32 within 20 million nodes
Fewest-candidates backtracking: all 132 grids, < 0.2 s each

Counting

The symmetry group of the grid (permutations of rows within a band, of bands, of columns within a stack, of stacks, and transposition) was built in GAP: order 3,359,232, 275 conjugacy classes. Burnside's lemma averages the number of grids fixed by each class, which gives the 5,472,730,538 essentially different grids of Russell and Jarvis.

Group order: 3,359,232
Conjugacy classes: 275
Tool: GAP