Sudoku Solver
Problem Statement
Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are marked with .. A valid solution must place digits 1 through 9 so that each row, each column, and each 3x3 box contains every digit exactly once. The board should be modified in place.
Input
A 9 x 9 character board containing digits and . for empty cells.
Output
No separate return value. Mutate board so every empty cell is filled with the unique valid Sudoku solution.
Constraints
- •
board.length == 9 - •
board[i].length == 9 - •
board[i][j] is a digit 1 through 9 or . - •
The input puzzle has exactly one solution
Examples
Example 1
board rows = [5,3,.,.,7,.,.,.,.], [6,.,.,1,9,5,.,.,.], [.,9,8,.,.,.,.,6,.], [8,.,.,.,6,.,.,.,3], [4,.,.,8,.,3,.,.,1], [7,.,.,.,2,.,.,.,6], [.,6,.,.,.,.,2,8,.], [.,.,.,4,1,9,.,.,5], [.,.,.,.,8,.,.,7,9]
solved rows = [5,3,4,6,7,8,9,1,2], [6,7,2,1,9,5,3,4,8], [1,9,8,3,4,2,5,6,7], [8,5,9,7,6,1,4,2,3], [4,2,6,8,5,3,7,9,1], [7,1,3,9,2,4,8,5,6], [9,6,1,5,3,7,2,8,4], [2,8,7,4,1,9,6,3,5], [3,4,5,2,8,6,1,7,9]Example 2
board has only one empty cell at row 8 column 8, and digit 9 is the only missing value in its row, column, and box
the empty cell becomes 9Learning Objectives
- Recognise Sudoku as board backtracking with row, column, and box constraints.
- Return a boolean from recursion so the first full valid board stops the search.
- Validate a digit against its row, column, and 3x3 box before placing it.
- Undo failed placements by resetting the cell to **.** before trying the next digit.
Intuition
Pattern Recognition
Sudoku is a constraint-satisfaction board problem. Each empty cell must receive one digit, but a digit is legal only if it does not already appear in the same row, column, or 3x3 box. That is exactly place, validate, recurse, undo.
The state is the partially filled board. The next choice is the next empty cell and one of digits 1 through 9. Before placing, validate the digit locally. If it is valid, write it into the cell and recurse. If the deeper call cannot finish the puzzle, reset the cell to . and try the next digit.
The key control-flow detail is the returned boolean. Sudoku asks for one complete solution and guarantees uniqueness, so once the recursion fills every cell, true bubbles back up and prevents any more undoing or sibling exploration.
Common mistakes
- ×Returning after the first invalid digit instead of trying the remaining digits for that empty cell.
- ×Forgetting to reset a failed cell to **.**, leaving stale digits that poison later branches.
- ×Checking the row and column but forgetting the 3x3 box.
- ×Continuing to search after a full solution is found, which can undo the solved board.
Algorithm Explanation
State
Each recursion frame works on the same mutable 9 x 9 board. The frame finds the next cell containing .. If no empty cell exists, the board is complete and the frame returns true.
Recursion tree
For the classic puzzle, the first empty cell is row 0 column 2. The tree branches over digits 1 through 9, but most digits are cut immediately by the row, column, or box. Suppose 1 is placed there; the solver continues to the next empty cell and may go many levels deeper before discovering a later cell with no valid digit. That failure returns false, causing each tentative placement in that branch to be reset to .. Eventually the branch with 4 at row 0 column 2 survives and the puzzle completes.
Pruning
A digit is pruned if it already appears in the target row, target column, or the 3x3 box whose top-left corner is (row / 3) * 3, (col / 3) * 3. These checks are constraint propagation: every placed digit immediately restricts future cells, and any cell with no legal digit forces the branch to backtrack.
Algorithm
- Search the board for the next . cell.
- If no empty cell exists, return true because the board is solved.
- For digits 1 through 9, test whether the digit is valid in the row, column, and box.
- Place the first valid candidate in the empty cell.
- Recurse to solve the rest of the board.
- If recursion returns true, return true immediately.
- Otherwise undo by resetting the cell to . and try the next digit.
- If no digit works, return false to force the previous cell to backtrack.
Solutions
Solution: Boolean backtracking with row, column, and box validation
Always solve the next empty cell. Try digits 1 through 9, place only digits that pass all three Sudoku constraints, and return true once the board is complete. Failed branches restore the cell to . before trying another digit.
Step-by-step
- The public method calls a boolean helper on the board.
- The helper scans for the next empty cell marked ..
- If no empty cell is found, return true because the board is solved.
- For that cell, try each digit from 1 through 9.
- A digit is valid only if it is absent from the row, absent from the column, and absent from the corresponding 3x3 box.
- Place a valid digit and recurse. If the recursive call succeeds, return true immediately.
- If it fails, reset the cell to . and try the next digit.
- Return false when no digit can solve the current cell.
O(9^m)
O(m)
m is the number of empty cells. Each empty cell may branch over up to 9 digits, and the recursion stack can contain one frame per empty cell.
Java implementation
Dry Run
Sample input
Classic Sudoku sample. Track the first empty cell and how failed guesses are undone before the successful branch continues.
| step | cell | choice | action (place/undo) | state |
|---|---|---|---|---|
| 1 | (0,2) | try 1 | place 1 | tentative row 0 is 5 3 1 . 7 . . . . |
| 2 | deeper branch | later cell has no digit | prune | branch with (0,2)=1 fails |
| 3 | (0,2) | 1 | undo to . | cell is empty again |
| 4 | (0,2) | try 2 | place 2 | another tentative branch begins |
| 5 | deeper branch | conflict appears | undo to . | return to (0,2) choices |
| 6 | (0,2) | try 4 | place 4 | row 0 becomes 5 3 4 . 7 . . . . |
| 7 | (0,3) | try 6 | place 6 | row 0 becomes 5 3 4 6 7 . . . . |
| 8 | final empty cell | only valid digit | place and stop | full board solved, true propagates |
The solver does not know that 4 is correct immediately. It learns by trying candidates, letting constraints propagate, and undoing any branch that makes a future cell impossible.
Interview Tips
Make the boolean return explicit. Without it, a valid solved board can be undone as recursion unwinds. Also keep validation simple and correct before optimizing: scan the row, column, and box with plain character comparisons, then reset to . on failure. If asked for speed, you can add row, column, and box bit masks, but the backtracking control flow stays the same.
Likely follow-ups
- How would you speed up validation with row, column, and box bit masks?
- How would you choose the next cell with the fewest candidates instead of the first empty cell?
- How would you detect whether a puzzle has more than one solution?
- How would you generate a valid Sudoku puzzle rather than solve one?
Similar Problems
Key Takeaways
- Sudoku is a constraint-satisfaction search over empty cells.
- Validate before placing so illegal digits never enter the deeper board state.
- Reset failed placements to **.** to keep sibling digit choices clean.
- Return **true** from the first complete solution to preserve the solved board.