The constraint model
Variables: each empty cell. Domain: digits 1–9. Constraints: each row, column and 3×3 box must contain all digits exactly once. This is a classic exact-cover problem. Donald Knuth's Algorithm X, implemented with dancing links, solves any valid Sudoku in milliseconds by exhaustively searching the constraint space.
Human strategies as heuristics
When humans solve Sudoku, they use strategies with names like 'naked pairs', 'X-Wing' and 'swordfish'. Each is a pattern that eliminates candidates from cells. In AI terms, these are constraint-propagation heuristics — rules that reduce the search space before backtracking is needed. A puzzle rated 'diabolical' is simply one where simple heuristics don't suffice.
Generation is harder than solving
Creating a Sudoku with a unique solution is computationally harder than solving one. Generators start with a full grid, remove numbers, and check uniqueness after each removal. The art is in controlling difficulty: too many givens and it's trivial; too few and it requires brute force. The best puzzle publications use human-rated difficulty curves.
From puzzle to paradigm
Sudoku's constraint structure appears in scheduling, resource allocation, circuit design and even radar target-association problems. When a radar has multiple targets and multiple tracks, assigning measurements to tracks is a constraint-satisfaction problem with additional probabilistic weights. The solver that handles your newspaper Sudoku is cousin to the one that keeps missile tracks from swapping.