Constraint satisfaction
A Sudoku solver fills a nine by nine grid so each row, column, and three by three box holds the digits one through nine exactly once. It is a classic constraint satisfaction problem solved cleanly by backtracking.
The basic loop
Scan for the next empty cell. For each digit one through nine, test whether placing it violates its row, column, or box. If valid, place it and recurse. If the recursion fails, erase the digit and try the next. If no digit works, return failure so the caller backtracks.
- A solved grid is reported when no empty cell remains.
- The erase step on failure is the un-choose that lets sibling digits be tried.
Making it fast
Naive cell order can explore enormous trees. A strong heuristic is most constrained cell first: always fill the empty cell with the fewest legal digits. Maintaining bitmask sets of used digits per row, column, and box turns validity checks into single bit operations and powers that heuristic cheaply.
Key idea
Sudoku is backtracking over empty cells with row, column, and box constraints, and filling the most constrained cell first with bitmask checks shrinks the search dramatically.