Benchmark five Sudoku solvers — Backtracking, MRV Backtracking, Constraint Propagation, Dancing Links, and Integer Linear Programming — across 400 puzzles spanning four difficulty tiers.
- Five solver implementations: Classic Backtracking, MRV Backtracking, Constraint Propagation, Dancing Links, and Integer Linear Programming
- 400 sampled puzzles (100 per difficulty tier: Easy, Medium, Hard, Expert)
- Each solver runs 5 times per puzzle; median solve time is recorded
- Every solution is validated against the known ground-truth answer
- Results exported to CSV for downstream analysis and visualization
| Package | Version |
|---|---|
| Python | ≥ 3.13 |
| PuLP | ≥ 3.3.0 |
HiGHS (highspy) |
≥ 1.14.0 |
| pandas | ≥ 3.0.2 |
| matplotlib | ≥ 3.10.8 |
| seaborn | ≥ 0.13.2 |
git clone https://github.com/th-tsai/sudoku-solver.git
cd sudoku-solver
python -m venv .venv
source .venv/bin/activate # Windows: .venv\Scripts\activate
pip install .Place the puzzle dataset at data/sudoku.csv. The file must contain three columns:
| Column | Description |
|---|---|
puzzle |
81-character string; . denotes an empty cell |
solution |
81-character string of the completed board |
difficulty |
Numeric Sudoku Explainer Rating (SER) |
This project uses 3 Million Sudoku Puzzles with Ratings by David Radcliffe (Kaggle).
The SER is a continuous score from Sudoku Explainer (Havard, 2008), reflecting the hardest logical technique needed to solve the puzzle without guessing. Puzzles are binned into four tiers:
| Tier | SER range | Techniques required |
|---|---|---|
| Easy | < 2.5 | Naked and hidden singles only |
| Medium | 2.5 – 5.0 | Locked candidates, naked/hidden pairs and triples |
| Hard | 5.0 – 6.5 | X-wings, swordfish, and similar pattern techniques |
| Expert | > 6.5 | Chains, forcing nets, or trial-and-error |
python main.pyThe script will:
- Sample 100 puzzles from each difficulty tier and cache them at
data/sampled_sudoku.csv - Run all five solvers on every puzzle (5 repetitions each) and print live results to the console
- Save timing and correctness data to
result/analysis_result.csv
sudoku-benchmark/
├── data/
│ ├── sudoku.csv # Full puzzle dataset
│ └── sampled_sudoku.csv # Auto-generated sample (400 puzzles)
├── result/
│ └── analysis_result.csv # Benchmarking output
├── solvers/
│ ├── backtracking.py # Classic and MRV backtracking
│ ├── constraint_propagation.py # Constraint propagation
│ ├── dancing_links.py # Dancing Links (DLX)
│ └── linear_programming.py # Integer linear programming
├── src/
│ └── utils.py # Board I/O, validation, and dataset helpers
├── main.py # Entry point and benchmarking loop
└── pyproject.toml
Classic backtracking is a depth-first search over the space of partial Sudoku assignments. The solver scans the board left-to-right and top-to-bottom, selecting the first empty cell, then tries digits 1–9 in order. If a placement is legal (no conflict in the same row, column, or 3×3 box) it advances; otherwise it backtracks to the previous decision point.
The implementation uses an explicit stack rather than recursion to avoid Python's call-stack depth limit.
The Minimum Remaining Values (MRV) heuristic improves classic backtracking by always selecting the empty cell with the fewest legal candidates rather than the first empty cell. Targeting the most-constrained variable first reduces the effective branching factor: contradictions are detected sooner and fewer dead-end branches are explored. The rest of the algorithm is identical to the classic variant.
Based on Peter Norvig's approach, the constraint propagation solver maintains an explicit candidate set for each cell and eagerly shrinks those sets as assignments propagate. Two inference rules are applied after each assignment:
- Naked single — if only one candidate remains in a cell, assign it and eliminate it from every peer cell.
- Hidden single — if a digit can appear in only one cell within a unit (row, column, or box), assign it immediately.
When propagation alone cannot resolve the board, the solver falls back to the MRV heuristic and recurses on independent deep copies of the candidate state. For easy and medium puzzles, propagation typically resolves the board entirely without any search.
Introduced by Donald Knuth (2000), the Dancing Links solver reformulates Sudoku as an Exact Cover problem and solves it with Algorithm X using a doubly-linked circular list structure that makes backtracking virtually allocation-free.
Every possible placement of digit d in cell (r, c) is a row in a binary matrix with four groups of columns (N = 81):
| Columns | Constraint |
|---|---|
| 0 – N−1 | Each cell is filled exactly once |
| N – 2N−1 | Each digit appears exactly once per row |
| 2N – 3N−1 | Each digit appears exactly once per column |
| 3N – 4N−1 | Each digit appears exactly once per box |
A solution is a subset of rows that covers every column exactly once. Cover removes a column and all intersecting rows by relinking their neighbours; Uncover reverses the operation in O(1) with no memory allocation. Algorithm X selects the column with the fewest active nodes (S-heuristic), covers it, and recurses; on failure it uncovers and tries the next row.
The ILP solver encodes Sudoku as a feasibility problem with no objective function.
Decision variables:
Constraints:
| Constraint | Meaning |
|---|---|
| Each cell contains exactly one digit | |
| Each digit appears exactly once per row | |
| Each digit appears exactly once per column | |
| Each digit appears exactly once per box | |
| Pre-filled clues are fixed |
The model is built with PuLP and solved with HiGHS.
All five solvers produced correct solutions on every puzzle in the benchmark — 100% accuracy across 400 puzzles and all difficulty tiers.
Median solve time per puzzle (seconds):
| Solver | Mean | Std | Median | Max |
|---|---|---|---|---|
| Dancing Links | 0.00175 | 0.00073 | 0.00150 | 0.0077 |
| Constraint Propagation | 0.00254 | 0.00119 | 0.00220 | 0.0119 |
| Linear Programming | 0.03221 | 0.00230 | 0.03160 | 0.0507 |
| Backtracking (MRV) | 0.38348 | 0.63802 | 0.16900 | 7.4475 |
| Backtracking (Classic) | 1.19461 | 2.87249 | 0.31425 | 29.212 |
Speed. Dancing Links is the fastest solver (median 1.5 ms), with Constraint Propagation close behind (2.2 ms). Both are roughly 100× faster than the backtracking variants at the median. Linear Programming sits in the middle at a nearly constant ~32 ms per puzzle.
Difficulty sensitivity. Backtracking runtimes degrade sharply as puzzle difficulty increases — the classic variant reaches 29 s on the hardest puzzles; MRV reduces the worst case to ~7.5 s. A log-linear regression of solve time against SER confirms steep positive slopes for both backtracking variants. Dancing Links, Constraint Propagation, and Linear Programming show near-zero slopes — their runtimes are effectively independent of difficulty.
Variance. The backtracking solvers have standard deviations larger than their means, reflecting a heavy right tail from occasional hard search trees. Dancing Links and Constraint Propagation are tightly clustered; on a log-scale histogram their distributions barely span a single order of magnitude across all difficulty tiers.
MRV improvement. The MRV heuristic reduces median backtracking time by ~2× and maximum time by ~4× by cutting the effective branching factor. The gain is most pronounced on expert puzzles, where classic backtracking wastes the most time on hopeless branches.
LP consistency. The ILP solver's runtime is dominated by fixed model-building and HiGHS startup cost rather than search. This makes it the most predictable solver in wall-clock time, at the cost of being ~14× slower than Dancing Links at the median.
Five solvers — Dancing Links, Constraint Propagation, Backtracking (Classic), Backtracking (MRV), and Integer Linear Programming — were benchmarked against 400 Sudoku puzzles spanning four difficulty tiers (easy through expert). All five achieved 100% correctness.
Performance separates cleanly into two regimes. Dancing Links and Constraint Propagation solve every puzzle in under 12 ms regardless of difficulty, with near-zero correlation between solve time and SER rating. ILP sits at a stable ~32 ms per puzzle, its cost dominated by fixed model-building overhead rather than search. Backtracking solvers are a different class: the classic variant reaches a median of 314 ms and a worst case of 29 s on expert puzzles; applying the MRV heuristic halves the median and cuts the maximum by 4×, but the heavy right tail persists.
The figures confirm these patterns visually: time distributions for Dancing Links and Constraint Propagation are tightly clustered on a log scale across all difficulty tiers, while backtracking distributions shift dramatically rightward as rating increases. The log-linear regression plots make the divergence explicit — backtracking slopes are steep and positive; all other solvers are near-flat.
The central takeaway is that algorithm choice, not implementation tuning, determines whether runtime scales with puzzle difficulty. Search-based approaches without strong propagation are fundamentally sensitive to problem hardness; constraint-propagation and exact-cover methods are not.
MIT © 2026 Tim