Code Implementation

class Solution:
    def solveSudoku(self, board):
        def is_valid(r, c, ch):
            for i in range(9):
                if board[r][i] == ch:
                    return False
                if board[i][c] == ch:
                    return False
                if board[3*(r//3) + i//3][3*(c//3) + i%3] == ch:
                    return False
            return True

        def solve():
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        for ch in '123456789':
                            if is_valid(i, j, ch):
                                board[i][j] = ch
                                if solve():
                                    return True
                                board[i][j] = '.'
                        return False
            return True

        solve()
      

class Solution {
public:
    bool isValid(vector<vector<char>>& board, int row, int col, char ch) {
        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;
    }

    bool solve(vector<vector<char>>& board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    for (char ch = '1'; ch <= '9'; ++ch) {
                        if (isValid(board, i, j, ch)) {
                            board[i][j] = ch;
                            if (solve(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }
};
      

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++) {
                if (board[i][j] == '.') {
                    for (char ch = '1'; ch <= '9'; ch++) {
                        if (isValid(board, i, j, ch)) {
                            board[i][j] = ch;
                            if (solve(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int col, char ch) {
        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;
    }
}
      

var solveSudoku = function(board) {
    function isValid(r, c, ch) {
        for (let i = 0; i < 9; i++) {
            if (board[r][i] === ch) return false;
            if (board[i][c] === ch) return false;
            if (board[3 * Math.floor(r / 3) + Math.floor(i / 3)][3 * Math.floor(c / 3) + i % 3] === ch) return false;
        }
        return true;
    }

    function solve() {
        for (let i = 0; i < 9; i++) {
            for (let j = 0; j < 9; j++) {
                if (board[i][j] === '.') {
                    for (let ch = 1; ch <= 9; ch++) {
                        let num = ch.toString();
                        if (isValid(i, j, num)) {
                            board[i][j] = num;
                            if (solve()) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    solve();
};
      

Problem Description

The Sudoku Solver problem asks you to fill a partially completed 9x9 Sudoku board so that it becomes a valid solution. The board is represented as a 2D array called board, where each cell contains a digit ('1'-'9') or a '.' indicating an empty cell.

• Each row must have the digits 1-9 with no repeats.
• Each column must have the digits 1-9 with no repeats.
• Each of the nine 3x3 sub-boxes must have the digits 1-9 with no repeats.

The input is guaranteed to have only one valid solution. You must fill the board in-place, modifying the input array directly. Do not return anything from your function.

Thought Process

At first glance, solving Sudoku seems like a brute-force problem: for each empty cell, try all digits and see which one fits. However, brute-force alone would be extremely slow because there are potentially billions of combinations.

To optimize, we realize that the process is about making decisions and backtracking when a decision leads to a dead-end. It's like navigating a maze: at each intersection (empty cell), we try each possible path (digit), but if we hit a wall (invalid board), we go back and try the next path.

The key insight is to use backtracking: try a digit, move forward, and if we later find a conflict, undo the choice and try the next digit. This way, we don't waste time exploring impossible paths.

Solution Approach

We use a recursive backtracking algorithm to fill the board. Here are the steps:

1. Find the next empty cell: Loop through the board to find a cell with '.'.
2. Try all digits 1-9: For the empty cell, try placing each digit from '1' to '9'.
3. Check if the digit is valid: For each digit, check if it does not already appear in the current row, column, or 3x3 sub-box.
4. Place the digit and recurse: If valid, fill the cell with the digit and recursively attempt to solve the rest of the board.
5. Backtrack if needed: If the recursive call fails (leads to an invalid state), reset the cell to '.' and try the next digit.
6. Finish when all cells are filled: If there are no empty cells left, the board is solved.

Design choices:

• We check validity by scanning the row, column, and box, which is O(1) per check for a 9x9 board.
• We use recursion to manage the state and backtrack efficiently.
• We modify the board in-place, as required by the problem.

Example Walkthrough

Suppose we have the following board ('.' indicates empty):

5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
---------------------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
---------------------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9
  

The algorithm starts at the first empty cell (row 0, col 2). It tries '1', '2', '3', ..., and finds '4' is valid. It fills '4' and moves to the next empty cell.

This process continues recursively. When it reaches a cell where no digit is valid, it backtracks: resets the previous cell to '.' and tries the next digit. This continues until the entire board is filled with valid digits.

The algorithm guarantees a solution because the input always has one valid answer.

Time and Space Complexity

Brute-force approach:

• For each empty cell, try 9 digits, leading to up to 9ⁿ possibilities (n = number of empty cells).
• This is infeasible for large n.

• Still worst-case O(9ⁿ), but in practice, most branches are pruned early due to invalid placements.
• For a 9x9 board with reasonable constraints, it's fast enough.
• Space complexity is O(1) extra (beyond the board), but recursion uses O(n) stack space for n empty cells.

Because the board is always 9x9, the constants are small and the algorithm is efficient in practice.

Summary

The Sudoku Solver problem is a classic application of backtracking. By trying each digit in each empty cell and backtracking on invalid choices, we efficiently fill the board. The key insight is to prune invalid paths early, avoiding unnecessary work. The solution is both elegant and practical, leveraging recursion and simple validity checks to solve a complex combinatorial puzzle.