AI SUDOKU
How a Sudoku Solver Works: Backtracking and Unique Solutions
Every puzzle in AI Sudoku is created and verified by the same core engine: a backtracking solver. It's a small, elegant algorithm — and understanding it explains why you can always trust that a puzzle is fair, solvable, and has exactly one answer.
Backtracking: Disciplined Trial and Error
Backtracking is depth-first search with an undo button. The solver walks the grid looking for the first empty cell, then tries digits 1 through 9 in turn. For each digit it asks one question: does this break a rule — is the same number already in this row, column, or 3×3 box?
- Find the next empty cell. If there are none, the grid is solved.
- Try a candidate digit that doesn't conflict with any peer cell.
- Place it and recurse to the next empty cell.
- If no digit works, backtrack: clear the cell and return to the previous one to try its next option.
Because it only ever places legal digits and reverses dead ends, the search is guaranteed to find a solution if one exists — and to exhaust every possibility if asked.
💡 Why it's fast enough: A naive search of all 981 grids is astronomically large, but constraint checking prunes the tree aggressively. Most cells have only a handful of legal options, so the solver reaches a full grid in milliseconds.
Generating a Puzzle
To make a puzzle, the engine runs the solver in reverse:
- Build a full solution. Run the solver on an empty grid, but shuffle the digit order so it produces a random completed board every time.
- Dig holes. Remove clues one at a time (in symmetric pairs, for that classic look), checking after each removal that the puzzle still has only one solution.
- Stop at the target. Keep removing until the difficulty's clue count is reached — about 45 for Easy, 34 for Medium, 28 for Hard.
The Uniqueness Test
This is the step that makes a puzzle trustworthy. After removing a clue, the engine runs a solution counter — the same backtracking search, but instead of stopping at the first solution it keeps going to see if a second exists. The moment it finds two, it knows the removal was unsafe and puts the clue back.
A puzzle with two or more solutions can't be solved by logic alone — at some point you'd have to guess. By rejecting every removal that breaks uniqueness, the generator guarantees a single answer, which is exactly what makes pure-logic solving possible.
💡 Counting trick: The counter caps out at two solutions. It never needs the exact total — only whether the answer is "one" or "more than one" — so it can bail out early and stay fast.
From Solver to Hint Engine
The same machinery powers the AI Hint button. Rather than brute-forcing to the answer, the hint engine mirrors how a person solves: it computes the candidates for every cell, applies logical eliminations, and finds the next forced move. We unpack those human techniques in The Logic Techniques Behind Every Sudoku — or, if you're just starting out, learn how to play Sudoku first.
How fast is it? We benchmarked three solvers
We ran this exact engine over 100 generated puzzles — 25 each from easy to expert — and compared three ways to solve them. The harness is open source, so every number below reproduces with node benchmark.js: github.com/lucian-devops/sudoku-solver.
On an expert puzzle, naive backtracking explores about 47,600 positions. The human-style logic a solver can apply first cracks it in around 3 — and clears easy and medium puzzles with zero guessing.
| Solver | Avg positions searched | On expert |
|---|---|---|
| Naive backtracking | 13,373 | 47,623 |
| Most-constrained-cell (MRV) | 159 | 376 |
| Logic (naked + hidden singles) | 2 | 3 |
Choosing which empty cell to try next — always the one with the fewest candidates — shrinks the search about 84×. Adding the naked- and hidden-single deductions the hint engine uses shrinks it a further ~80×, and clears easy and medium puzzles without a single guess. Most Sudoku never truly requires guessing; only the hardest tier does, and only barely.
Reproduce this. The generator, all three solvers, and the benchmark are on GitHub — with a live solver you can paste any puzzle into: github.com/lucian-devops/sudoku-solver.