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.