Sudoku Solver
Fill the empty cells of a partially completed 9 × 9 Sudoku grid so that every row, column and 3 × 3 box contains each digit 1–9 exactly once. The given puzzle has exactly one solution.
- board is 9 × 9
- Cells contain a digit or "."
- A unique solution exists
- Constraint satisfaction with undoable placements
- Try each digit in an empty cell, recurse, revert
- Fast validity checks via row/column/box sets
Enumerating every arrangement is exponential, so tiny bounds plus "all" or "any valid" wording mean search the decision tree: choose, recurse, un-choose. Pruning invalid partial states early (a queen already attacked, a sum already exceeded) is what makes it practical.
Keep boolean tables row[9][10], col[9][10] and box[9][10] marking used digits. Find the next empty cell, try each digit not used in its row, column or box, place it and mark the tables, then recurse. If the recursion succeeds, stop; otherwise erase the digit and try the next. Reaching the end of the grid means the puzzle is solved.
- Choosing the empty cell with the fewest candidates (MRV heuristic) drastically reduces branching. Dancing Links (Algorithm X) solves it as exact cover.