Sudoku Solver | Backtracking

leetcode.com

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