Sudoku Solver

This visualization shows a backtracking algorithm solving a standard 9*9 Sudoku puzzle. The solver fills in empty cells one at a time, checking constraints at each step, and backtracks when it reaches a dead end. Sudoku, whose name means "single number" in Japanese, rose to global popularity in 2004 after British newspaper The Times began publishing the puzzles daily. Although the modern form was designed by Howard Garns in 1979 under the name "Number Place," the mathematical foundations of Sudoku connect to Latin squares studied by Leonhard Euler in the 18th century.

Historical Context

Latin squares -- grids where each symbol appears exactly once per row and column -- were systematically studied by Euler in 1783. Sudoku adds the constraint that each 3*3 sub-grid (box) must also contain each digit exactly once, making it a specialized constrained Latin square. Mathematicians have determined there are 6,670,903,752,021,072,936,960 valid completed Sudoku grids (after accounting for symmetries, 5,472,730,538 essentially different grids). The minimum number of given clues required for a unique solution is 17, a result proven computationally in 2012 by Gary McGuire and colleagues.

How It Works

1. Find empty cell: Scan the grid for the next empty cell, typically proceeding left to right, top to bottom.
2. Try values 1-9: For each candidate value, check if it violates any Sudoku constraint -- no duplicate in the same row, column, or 3*3 box.
3. Place and recurse: If the value is valid, place it in the cell and recursively try to solve the rest of the puzzle by moving to the next empty cell.
4. Backtrack: If no valid value works for a cell (all digits 1-9 create a conflict), clear the cell and return to the previous cell to try a different value. This systematic unwinding ensures completeness.
5. Solved: When all 81 cells are filled without conflicts, the puzzle is solved.

The constraint check at each step is the critical operation. A naive implementation checks the entire row, column, and box for duplicates. A more efficient approach maintains sets or bitmasks for each row, column, and box, enabling O(1) constraint verification per candidate value.

Complexity

In practice, constraint checking prunes the search tree dramatically, and most well-formed puzzles (those with a unique solution and sufficient clues) are solved in milliseconds even by a naive backtracker. Harder puzzles with fewer clues or deliberate anti-backtracking constructions can require exploring thousands of dead-end branches.

Sudoku as a Constraint Satisfaction Problem

Formally, a Sudoku puzzle is a Constraint Satisfaction Problem (CSP) with 81 variables (the cells), domains of size 1-9, and 27 all-different constraints (9 rows, 9 columns, 9 boxes). This CSP perspective opens the door to powerful solving techniques beyond simple backtracking: arc consistency (AC-3), naked pairs, hidden singles, and more advanced constraint propagation methods. Peter Norvig's famous essay "Solving Every Sudoku Puzzle" demonstrates how combining constraint propagation with backtracking produces a solver capable of handling even the hardest known puzzles in milliseconds.

When to Use

Sudoku solving demonstrates pure backtracking -- a systematic trial-and-error approach with constraint checking. The same technique applies to many constraint satisfaction problems: scheduling, register allocation, frequency assignment, and general puzzle solving. Compare this basic approach with the MRV + LCV heuristic version to see how smart variable and value ordering can drastically reduce the search space. The progression from naive backtracking to heuristic-enhanced solving mirrors the evolution of practical CSP solvers used in industry.