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

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