MANG Problem #10: Sudoku Solver (Hard)

1. Problem Statement

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

2. Approach: Recursive Backtracking

graph TD
    Start[Empty Cell] --> Try1[Try 1]
    Start --> Try2[Try 2]
    Start --> TryN[...]
    Try1 --> Valid{Valid?}
    Valid -- No --> Back[Backtrack]
    Valid -- Yes --> Next[Next Empty Cell]
    Next --> Win[Solved!]
    Next --> Lose[Dead End]
    Lose --> Back

We treat every empty cell as a decision point.

1. Find Empty: Find the next cell marked with ..
2. Try Choices: Try placing digits 1 through 9.
3. Check Constraints: For each digit, check if it's valid according to row, column, and 3x3 box rules.
4. Recurse: If valid, move to the next empty cell.
5. Backtrack: If no digit works, "un-place" the digit (set back to .) and return to the previous cell.

3. Java Implementation

public void solveSudoku(char[][] board) {
    solve(board);
}

private boolean solve(char[][] board) {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] == '.') {
                for (char d = '1'; d <= '9'; d++) {
                    if (isValid(board, r, c, d)) {
                        board[r][c] = d;
                        if (solve(board)) return true; // Success!
                        board[r][c] = '.'; // Backtrack
                    }
                }
                return false; // Exhausted all digits for this cell
            }
        }
    }
    return true; // No empty cells left
}

private boolean isValid(char[][] board, int row, int col, char c) {
    for (int i = 0; i < 9; i++) {
        if (board[i][col] == c) return false; // Column check
        if (board[row][i] == c) return false; // Row check
        
        // 3x3 Box check
        int boxRow = 3 * (row / 3) + i / 3;
        int boxCol = 3 * (col / 3) + i % 3;
        if (board[boxRow][boxCol] == c) return false;
    }
    return true;
}

4. 5-Minute "Video-Style" Walkthrough

1. The "Aha!" Moment: Think of Sudoku as a tree. The root is the starting board. Each empty cell branches into 9 possibilities. Most branches are "dead ends" that we prune early using isValid.
2. The Pruning: We don't wait until the board is full to check if it's a valid Sudoku. We check every single digit as we place it. This reduces the search space from $9^{81}$ to something manageable.
3. The Box Trick: Finding the top-left corner of a 3x3 box is easy using integer division: (row / 3) * 3.

5. Interview Discussion

• Interviewer: "What is the time complexity?"
• You: "In the absolute worst case, it's $9^{81}$, but because of Sudoku constraints, the actual number of states explored is much smaller. It is constant time $O(1)$ since the board size is fixed at 9x9."
• Interviewer: "How can we optimize?"
• You: "We can use Bitmasks to speed up the isValid check, or use the Minimum Remaining Values (MRV) heuristic—pick the cell with the fewest possible valid digits first to prune the tree even faster."

Read Next

• MANG Problem #11: Longest Valid Parentheses
• MANG Problem #12: N-Queens 埋