Sudoku Solver

Solve the Sudoku puzzle by filling empty cells while respecting Sudoku's rules using array scanning and backtracking.

Problem Statement

You are given a partially filled 9x9 Sudoku grid where empty cells are represented by the '.' character. Your task is to fill the grid to satisfy all Sudoku constraints: each number from 1 to 9 must appear exactly once in each row, column, and 3x3 subgrid. The board is guaranteed to have only one solution.

Implement an algorithm that fills the grid, ensuring all constraints are met. The input board contains numbers from '1' to '9' and the '.' symbol for empty cells. You must modify the board in place and return the completed grid, solving the puzzle efficiently.

Examples

Example 1

Input: board = [["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"]]

Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

The input board is shown above and the only valid solution is shown below:

Constraints

board.length == 9
board[i].length == 9
board[i][j] is a digit or '.'.
It is guaranteed that the input board has only one solution.

Solution Approach

Backtracking Approach

The primary technique for solving the Sudoku puzzle is backtracking. For each empty cell, attempt to place numbers from 1 to 9. Use hash sets to track used numbers in rows, columns, and subgrids, eliminating invalid options. Recursively try filling cells, backtracking when a conflict arises, until the entire grid is solved.

Array Scanning for Efficient Validation

Array scanning is used to efficiently validate potential number placements. Iterate over the grid to check for conflicts in the corresponding row, column, and subgrid using hash sets. This helps to quickly reject invalid placements, improving the speed of the backtracking process.

Optimizing with Hash Lookup

Hash lookups are employed to quickly track the numbers that have already been placed in each row, column, and subgrid. This prevents unnecessary re-checking and speeds up the backtracking process. By using hash sets, we reduce the time complexity of validating a placement.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the backtracking approach, as we attempt to fill each empty cell while checking constraints. In the worst case, the time complexity is O(9^81), but early exits and pruning via hash sets typically improve performance. Space complexity is O(1) as the board is modified in place, with hash sets used for tracking constraints during recursion.

What Interviewers Usually Probe

Do you understand how backtracking helps with solving constraint satisfaction problems like Sudoku?
Can you explain how using hash sets optimizes the time complexity of the backtracking approach?
Will you be able to handle edge cases, such as when the Sudoku grid is almost solved but still contains a few empty cells?

Common Pitfalls or Variants

Common pitfalls

Not properly updating hash sets after placing numbers, which could lead to incorrect checks for subsequent placements.
Overcomplicating the backtracking approach by not pruning branches early enough, leading to unnecessary recursion.
Failing to correctly handle the constraints of the 3x3 subgrids, which could result in invalid Sudoku solutions.

Follow-up variants

Solve a Sudoku puzzle where the board contains multiple solutions (not guaranteed to have one solution).
Implement a Sudoku solver using a constraint propagation technique like AC-3 or similar.
Create a Sudoku solver that generates random Sudoku puzzles while ensuring a unique solution.

FAQ

How does backtracking help in solving the Sudoku puzzle?

Backtracking helps by testing potential solutions for each empty cell, recursively exploring possible placements and undoing incorrect choices until the grid is solved.

What role do hash sets play in solving the Sudoku puzzle?

Hash sets efficiently track numbers used in each row, column, and 3x3 subgrid, enabling quick validation and reducing the time complexity of the backtracking approach.

What is the time complexity of solving Sudoku with backtracking?

The time complexity in the worst case is O(9^81), but optimization with hash lookups and pruning helps significantly reduce the actual runtime.

How can I improve the performance of the Sudoku solver?

To improve performance, optimize the backtracking process by reducing unnecessary recursion through pruning and leveraging hash sets to quickly track constraints.

Are there any edge cases I should consider when solving the Sudoku puzzle?

Edge cases include handling sparse grids with very few filled cells, ensuring valid placements for each cell, and properly managing hash sets to avoid conflicts.

terminal

Solution

Solution 1: Backtracking

We use arrays $\textit{row}$, $\textit{col}$, and $\textit{box}$ to record whether each number has appeared in each row, each column, and each 3x3 sub-box, respectively. If the number $i$ has appeared in row $r$, column $c$, or the $b$-th 3x3 sub-box, then $\text{row[r][i]}$, $\text{col[c][i]}$, and $\text{box[b][i]}$ are all set to $true$.

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def dfs(k):
            nonlocal ok
            if k == len(t):
                ok = True
                return
            i, j = t[k]
            for v in range(9):
                if row[i][v] == col[j][v] == block[i // 3][j // 3][v] == False:
                    row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
                    board[i][j] = str(v + 1)
                    dfs(k + 1)
                    row[i][v] = col[j][v] = block[i // 3][j // 3][v] = False
                if ok:
                    return

        row = [[False] * 9 for _ in range(9)]
        col = [[False] * 9 for _ in range(9)]
        block = [[[False] * 9 for _ in range(3)] for _ in range(3)]
        t = []
        ok = False
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    t.append((i, j))
                else:
                    v = int(board[i][j]) - 1
                    row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
        dfs(0)

Continue Practicing

#36 valid sudoku #73 set matrix zeroes #79 word search