Sudoku Solver

Hard· backtracking· constraint pruning

Problem

Fill the empty cells (marked ".") of a 9x9 Sudoku so that each row, each column, and each 3x3 box contains the digits 1-9 exactly once. The puzzle is guaranteed to have exactly one solution, and you modify the board in place.

Examples

Input: board = a 9x9 grid of digits and "." with a unique solution

Output: the same grid with every "." replaced

Every row, column and 3x3 box of the result is a permutation of 1-9 and agrees with the given clues.

Constraints

• board is 9 x 9
• Each cell is a digit 1-9 or "."
• The puzzle has exactly one solution

Hints & approach

Hint 1

Find an empty cell and try each digit that does not clash with its row, column or box.

Hint 2

Keep bitmasks or boolean tables per row, column and box so a clash check is O(1).

Hint 3

If no digit fits, undo and return false so the caller tries its next digit.

Approachtry the hints first

Precompute which digits are used in each row, column and box. Recursively pick the next empty cell; for each digit 1-9 that is free in all three of its groups, write it, mark the tables, and recurse. If the recursion reports success, stop; otherwise clear the cell and the marks and try the next digit. Returning false when no digit fits is what triggers backtracking. Choosing the empty cell with the fewest legal digits first cuts the search dramatically, though the plain version is already fast on 9x9.

Time O(9^m), m = empty cells (bounded constant for 9x9) · Space O(m) recursion

← PreviousN-Queens DoneBack to Recursion & backtracking