Problem Statement
Given a partially filled Sudoku board, fill all empty cells so that:
- Every row contains digits 1-9
- Every column contains digits 1-9
- Every 3×3 box contains digits 1-9
Return the solved board.
Brute Force Intuition
For every empty cell:
Try digits 1 to 9
After filling the board:
Check if Sudoku is valid
This leads to enormous possibilities.
Moving Towards the Optimal Approach
Instead of filling everything first:
For every empty cell:
Try digits 1 to 9
Immediately check validity.
If valid:
Place digit
Recurse
Otherwise:
Try next digit
Pattern Recognition
Whenever you see:
- Fill grid
- Constraints
- Multiple choices at each step
Think:
Backtracking + Validation
Key Observation
For an empty cell:
'.'
Try:
1
2
3
...
9
Only continue if placing the digit keeps Sudoku valid.
Optimal Java Solution
class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (board[row][col] == '.') {
for (char ch = '1'; ch <= '9'; ch++) {
if (isValid(row, col, ch, board)) {
board[row][col] = ch;
if (solve(board))
return true;
board[row][col] = '.';
}
}
return false;
}
}
}
return true;
}
private boolean isValid(int row,
int col,
char ch,
char[][] board) {
for (int i = 0; i < 9; i++) {
if (board[row][i] == ch)
return false;
if (board[i][col] == ch)
return false;
if (board[3 * (row / 3) + i / 3]
[3 * (col / 3) + i % 3] == ch)
return false;
}
return true;
}
}
Dry Run
Find first empty cell:
5 3 .
6 . .
. 9 8
Try:
1 ❌
2 ❌
3 ❌
4 ✅
Place:
5 3 4
6 . .
. 9 8
Move to next empty cell.
Continue until board is solved.
Why Backtracking Works?
For every empty cell:
Try all valid digits
If a digit eventually leads to failure:
Undo
Try next digit
This systematically explores all valid possibilities.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(9^(Empty Cells)) |
| Space Complexity | O(81) |
Interview One-Liner
For every empty cell, try digits 1-9. If a digit is valid, place it and recursively solve the remaining board. Backtrack whenever a dead end is reached.
Pattern Learned
Fill Grid
+
Validity Constraint
+
Multiple Choices
=> Backtracking
Similar Problems
- Sudoku Solver
- N Queens
- Rat in a Maze
- Crossword Puzzle
- Word Search
- Graph Coloring