Brute Force Approach for Sudoku Solver

A naive brute force approach attempts to generate every possible configuration of the board until a valid solution is found.

1. Identify all $M$ empty cells.
2. For the first empty cell, try filling it with '1'. Then move to the second, try '1', and so on.
3. Once all cells are filled, scan the entire board to check if it satisfies the Sudoku rules (unique rows, columns, and sub-boxes).
4. If the check fails, change the last cell to '2' and repeat.

Pseudo-code:

text
function bruteForce(index):
    if index == number_of_empty_cells:
        return isValidBoard()
    
    for digit in '1' to '9':
        fill cell[index] with digit
        if bruteForce(index + 1):
            return true
            
    return false

Why it fails: The time complexity is $O(9^M)$, where $M$ is the number of empty cells. If a board has 50 empty cells, the algorithm attempts up to $9^{50}$ combinations. This approach fails due to Time Limit Exceeded because it fills the entire board before checking validity. It wastes massive computational resources exploring branches that are obviously invalid (e.g., placing two '5's next to each other early in the process).

Core Insight for Sudoku Solver

The core insight that optimizes the naive approach is pruning. Instead of validating the board only after it is full, we validate the board before making a placement.

The invariant we must maintain is: At every step of the recursion, the board must remain valid according to Sudoku rules.

If we are at cell $(r, c)$ and decide to place the number '5', we immediately check:

1. Is '5' already in row $r$?
2. Is '5' already in column $c$?
3. Is '5' already in the $3 \times 3$ sub-box containing $(r, c)$?

If the answer to any of these is "yes," we do not place '5' and do not recurse further down that path. We prune the tree immediately. This drastically reduces the search space from $9^M$ to a much smaller subset of valid configurations.

Visual Description: Imagine the algorithm as traversing a decision tree. The root is the initial board. At the first empty cell, the tree splits into up to 9 branches (digits 1-9).

• If we pick branch '3' and it violates a row constraint, we cut that branch off immediately.
• If '3' is valid, we move down that edge to the next node (the next empty cell).
• If we reach a node where no digits 1-9 can be placed validly, we return (backtrack) to the parent node, undo our last move, and try the next digit.

Execution Flow

Let's trace the logic for a simplified scenario:

1. Start: The algorithm is called on the board.
2. Find Empty: It finds the first empty cell at (0, 2).
3. Try Choices: It attempts to place '1'.
   • It checks row 0, column 2, and the top-left $3 \times 3$ box.
   • Suppose '1' exists in row 0. The check fails.
4. Try Next: It attempts to place '2'.
   • Constraints pass. It writes '2' into (0, 2).
5. Recurse: It calls solve() again.
   • The function finds the next empty cell at (0, 3).
   • It tries '1'. Fails constraints.
   • It tries '2'. Fails constraints (we just placed a 2 in the same row).
   • ...
   • Suppose all digits 1-9 fail for (0, 3).
6. Backtrack: The recursive call for (0, 3) returns false.
   • Control returns to the instance handling (0, 2).
   • Reset: The algorithm resets (0, 2) from '2' back to '.'.
   • It continues the loop for (0, 2) trying digit '3'.

This process continues until the board is completely filled.

Proof of Correctness

The algorithm implements a Depth-First Search (DFS) on the state space of possible Sudoku boards.

1. Completeness: Because it systematically tries every valid digit for every empty cell, it explores all potential valid configurations.
2. Soundness: The isValid check ensures that we never build upon an invalid state. Therefore, if we reach a state with no empty cells, it must be a valid solution.
3. Termination: The problem guarantees a unique solution exists. The search space is finite ($9 \times 9$ grid), so the recursion is guaranteed to terminate either by finding the solution or exhausting possibilities (though the latter won't happen given the problem constraints).

Reference Implementation

C++ Solution for LeetCode 37

cpp
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }

private:
    bool solve(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // Find the first empty cell
                if (board[i][j] == '.') {
                    // Try digits 1-9
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c; // Place choice
                            
                            if (solve(board)) // Recurse
                                return true; // Found solution
                            
                            board[i][j] = '.'; // Backtrack
                        }
                    }
                    return false; // No digit worked for this cell
                }
            }
        }
        return true; // All cells filled
    }

    bool isValid(vector<vector<char>>& board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            // Check row
            if (board[row][i] == c) return false;
            // Check column
            if (board[i][col] == c) return false;
            // Check 3x3 sub-box
            // Formula to map linear index i (0-8) to sub-box coordinates
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
        }
        return true;
    }
};

Java Solution for LeetCode 37

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

    private boolean solve(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // Look for empty cell
                if (board[i][j] == '.') {
                    // Try placing digits 1-9
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c; // Place
                            
                            if (solve(board)) {
                                return true; // Solution found
                            }
                            
                            board[i][j] = '.'; // Backtrack
                        }
                    }
                    return false; // No valid placement found, trigger backtrack
                }
            }
        }
        return true; // Board is full
    }

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

Python Solution for LeetCode 37

python
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place.
        """
        self.solve(board)

    def solve(self, board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for char in "123456789":
                        if self.isValid(board, i, j, char):
                            board[i][j] = char # Place
                            
                            if self.solve(board): # Recurse
                                return True
                            
                            board[i][j] = '.' # Backtrack
                    return False
        return True

    def isValid(self, board, row, col, char):
        for i in range(9):
            # Check row
            if board[row][i] == char:
                return False
            # Check column
            if board[i][col] == char:
                return False
            # Check 3x3 block
            # Logic: (row // 3) * 3 gives the starting row index of the block
            # i // 3 iterates 0, 0, 0, 1, 1, 1, 2, 2, 2
            blk_row = 3 * (row // 3) + i // 3
            blk_col = 3 * (col // 3) + i % 3
            if board[blk_row][blk_col] == char:
                return False
        return True

• Mistake: Using complex if/else logic to determine the sub-box boundaries.
• Why: It makes the code verbose and prone to off-by-one errors.
• Correction: Use the formula (row / 3) * 3 to find the top-left corner of the block. Iterate k from 0 to 8, accessing board[startRow + k/3][startCol + k%3].