Three Sudoku solvers, one engine, 34,000 fewer guesses

The Sudoku generator that ships in my puzzle game is a plain randomised-backtracking solver. It works, but "it works" is a vibe, not a number. So I pointed three different solving strategies at the exact same engine and counted how hard each one actually has to search. The engine and the benchmark are open source. Every node count below is deterministic - clone it, run node benchmark.js , and you get the same figures I did. The setup A grid is a flat array of 81 cells (0 = empty). The corpus is 40 puzzles - 10 each of Easy, Medium, Hard and Expert - generated by the shipped generator with fixed seeds, so the exact same 40 puzzles rebuild every run. The metric I care about is search nodes: how many cells the solver has to guess at and recurse on. Wall-clock time depends on your laptop; node counts don't. (Times below are from my machine, rounded, for flavour only.) Three strategies, all solving the identical puzzles: - Naive backtracking - the algorithm the game actually ships. Fill the next empty cell, try 1-9, recurse, undo on failure. - MRV backtracking - same idea, but always branch on the cell with the fewest candidates first (a most-constrained-variable heuristic). - Logic (constraint propagation) - before ever guessing, repeatedly apply naked singles and hidden singles to deduce forced cells. This is the same kind of reasoning the game's AI-hint button explains, only run to exhaustion. Before comparing anything, the harness asserts all three return the same solution on all 40 puzzles. Mismatches: 0. So we're comparing correct solvers, not fast-but-wrong ones. The numbers Average search nodes per puzzle (node benchmark.js , 10 puzzles/tier, seeded): | difficulty | naive backtracking | MRV backtracking | logic (propagation) | |---|---|---|---| | Easy | 59 | 37 | 1 | | Medium | 598 | 55 | 1 | | Hard | 10,750 | 380 | 2 | | Expert | 103,932 | 238 | 3 | | all 40 | 28,835 | 177 | 2 | A few things jump out: - Naive backtracking falls off a cliff on Expert - ~104k search nodes on average (~9 ms), versus 59 on Easy. Fewer clues means longer, blinder guessing chains. - MRV flattens that cliff. Overall it explores ~163× fewer nodes than naive (28,835 → 177). Just always branching on the most-constrained cell keeps the whole search cheap. - Logic barely searches at all. Easy and Medium puzzles solve in a single node - zero guessing, pure deduction. Even Expert takes ~3. Overall that's 28,835 → 2 , roughly 14,000× fewer search nodes than naive, and on Expert alone,103,932 → 3 - about 34,000×. One honest quirk: for MRV, Expert (238) actually edges out Hard (380). With only ~24 clues, Expert grids give constraint propagation more to bite on, and with 10 puzzles per tier there's real sample variance. I'm leaving it in rather than cherry-picking a monotonic table. Why the gap is so big Naive backtracking treats every empty cell as equally worth guessing, so on a sparse grid it wanders down enormous doomed branches before backing out. MRV never guesses on a cell with five options when one with two is available - most of the tree simply never gets built. And logic solving asks a different question entirely: not "which value do I try here?" but "which cell is already forced?" On anything up to Hard, that question has an answer often enough that you never have to guess. That last point is also why the game feels fair: the same singles the propagation solver uses to avoid guessing are the moves the hint engine points at, so every puzzle is solvable by reasoning, not luck. Reproduce it git clone https://github.com/lucian-devops/sudoku-solver cd sudoku-solver node benchmark.js # the table above (deterministic node counts) node benchmark.js 50 # 50 puzzles/tier if you want steadier averages engine.js is the actual generator/solver from the live game, extracted verbatim; the instrumented solver variants (node counters, MRV, propagation) live in benchmark.js so the shipped module stays exactly what players get. If you want to see the shipped solver working on a real board, there's a full write-up with the same numbers here: How a Sudoku solver works → - or just play a puzzle and hit the hint button to watch the propagation logic name each move. Numbers computed from the real shipped engine, not a reimplementation. Corpus and counts are seeded and reproducible. Top comments (0)