LeetCode 37: Sudoku Solver Solution in Python Explained
Problem Statement
LeetCode 37, Sudoku Solver, is a hard-level problem where you’re given a 9x9 Sudoku board represented as a 2D list board. Your task is to fill the board with digits 1-9 such that each row, column, and 3x3 sub-box contains every digit exactly once. The board contains some filled cells (digits 1-9) and empty cells (denoted by .). Modify the board in-place to solve the puzzle, assuming a unique solution exists.
Constraints
- board.length == 9: Grid is 9x9.
- board[i].length == 9: Each row has 9 elements.
- board[i][j] is a digit 1-9 or ..
- The input board has a unique solution.
Example
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"]]
Explanation: The board is filled to satisfy Sudoku rules.
Understanding the Problem
How do you solve LeetCode 37: Sudoku Solver in Python? Given a partially filled 9x9 board, fill all . cells with digits 1-9 so that no row, column, or 3x3 sub-box has duplicates. For the example, start with a mix of digits and dots, and end with a fully solved board. We’ll explore two approaches: a Backtracking with Hash Sets Solution (optimal and primary) and an Alternative with Bit Manipulation (space-efficient but complex). The backtracking method tries digits and backtracks when rules are violated.
Solution 1: Backtracking with Hash Sets Approach (Primary)
Explanation
Use backtracking to fill empty cells, checking validity with hash sets for rows, columns, and boxes. Try digits 1-9 at each empty cell, recurse forward if valid, and backtrack if stuck.
Here’s a conceptual flow:
Cell (0,2): Try 4, valid, proceed.
Cell (0,3): Try 6, valid, proceed.
If invalid later, backtrack and try next digit.
- Initialize Tracking Sets.
- Sets for rows, columns, boxes with pre-filled digits.
- Find Empty Cell.
- Locate next . to fill.
- Backtrack.
- Try digits, check validity, recurse or backtrack.
- Solve In-Place.
Step-by-Step Example
Example: Simplified 4x4 Board
For simplicity, use a 4x4 board (rules adjusted):
[["1","2",".","."]
,["3",".",".","4"]
,[".",".","4","."]
,[".","3",".","1"]]
- Goal: Solve the board.
- Result: e.g., [["1","2","3","4"],["3","4","1","2"],["2","1","4","3"],["4","3","2","1"]].
- Start: Initialize sets with filled cells.
- Step 1: Sets: row[0] = {1,2}, col[0] = {1,3}, box[0][0] = {1,3}, etc.
- Step 2: Find empty: (0,2), try "3".
- row[0] = {1,2,3}, col[2] = {3}, box[0][1] = {3}, valid.
- Step 3: Next empty: (0,3), try "4".
- row[0] = {1,2,3,4}, col[3] = {4}, box[0][1] = {3,4}, valid.
- Step 4: (1,1), try "4".
- row[1] = {3,4}, col[1] = {2,4}, box[0][0] = {1,3,4}, valid.
- Step 5: Continue, e.g., (1,2), try "1", valid, proceed.
- Step 6: If stuck (e.g., no valid digit), backtrack, adjust earlier choice.
- Finish: Board solved, return.
How the Code Works (Backtracking)
Here’s the Python code with line-by-line explanation:
def solveSudoku(board: list[list[str]]) -> None:
# Line 1: Initialize tracking sets
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [[set() for _ in range(3)] for _ in range(3)]
# Line 2: Fill sets with initial values
for i in range(9):
for j in range(9):
if board[i][j] != '.':
num = board[i][j]
rows[i].add(num)
cols[j].add(num)
boxes[i // 3][j // 3].add(num)
# Line 3: Backtracking function
def backtrack(i: int, j: int) -> bool:
# Line 4: Move to next row if end of current
if j == 9:
i += 1
j = 0
# Line 5: Board filled, solution found
if i == 9:
return True
# Line 6: Skip filled cells
if board[i][j] != '.':
return backtrack(i, j + 1)
# Line 7: Try digits 1-9
for num in '123456789':
box_i, box_j = i // 3, j // 3
# Line 8: Check validity
if (num not in rows[i] and
num not in cols[j] and
num not in boxes[box_i][box_j]):
# Line 9: Place digit
board[i][j] = num
rows[i].add(num)
cols[j].add(num)
boxes[box_i][box_j].add(num)
# Line 10: Recurse
if backtrack(i, j + 1):
return True
# Line 11: Backtrack
board[i][j] = '.'
rows[i].remove(num)
cols[j].remove(num)
boxes[box_i][box_j].remove(num)
return False
# Line 12: Start solving from (0,0)
backtrack(0, 0)
Alternative: Backtracking with Bit Manipulation
Explanation
Use bitmaps instead of sets to track digits, reducing space. Each bitmap (integer) uses bits 0-8 for digits 1-9. Backtrack similarly, toggling bits.
- Initialize Bitmaps.
- Backtrack with Bits.
- Solve In-Place.
Step-by-Step Example (Alternative)
For 4x4 board:
- Start: rows, cols, boxes as bitmaps.
- Step 1: (0,0) = "1", rows[0] |= 1 << 0, etc.
- Step 2: (0,2), try "3", bit 2, check and set, proceed.
- Finish: Solved with bit operations.
How the Code Works (Bit Manipulation)
def solveSudokuBit(board: list[list[str]]) -> None:
# Line 1: Initialize bitmaps
rows = [0] * 9
cols = [0] * 9
boxes = [[0] * 3 for _ in range(3)]
# Line 2: Set initial bits
for i in range(9):
for j in range(9):
if board[i][j] != '.':
num = int(board[i][j]) - 1
bit = 1 << num
rows[i] |= bit
cols[j] |= bit
boxes[i // 3][j // 3] |= bit
# Line 3: Backtracking function
def backtrack(i: int, j: int) -> bool:
if j == 9:
i += 1
j = 0
if i == 9:
return True
if board[i][j] != '.':
return backtrack(i, j + 1)
for num in range(9):
bit = 1 << num
box_i, box_j = i // 3, j // 3
if not (rows[i] & bit or cols[j] & bit or boxes[box_i][box_j] & bit):
board[i][j] = str(num + 1)
rows[i] |= bit
cols[j] |= bit
boxes[box_i][box_j] |= bit
if backtrack(i, j + 1):
return True
board[i][j] = '.'
rows[i] &= ~bit
cols[j] &= ~bit
boxes[box_i][box_j] &= ~bit
return False
# Line 4: Start solving
backtrack(0, 0)
Complexity
- Hash Sets:
- Time: O(9^81) – Worst-case backtracking (exponential), but practical due to pruning.
- Space: O(1) – Fixed 81 cells, 27 sets.
- Bit Manipulation:
- Time: O(9^81) – Same worst-case.
- Space: O(1) – Fixed 27 integers.
Efficiency Notes
Both are exponential in theory, but backtracking prunes branches, making them practical. Hash Sets are more readable; Bit Manipulation saves space.
Key Insights
Tips to master LeetCode 37:
- Backtrack Smartly: Try, place, recurse, undo.
- Track Efficiently: Sets or bits for quick validation.
- In-Place: Modify board directly.
Additional Example
For [[".","2","."],[".",".","1"],["1",".","."]] (3x3):
- Goal: Solve it.
- Backtracking: Fill valid digits, e.g., [["3","2","1"],["2","1","3"],["1","3","2"]].
- Result: Solved board.
Edge Cases
- All Filled: No . – Already valid.
- Single Cell: [["."]] – Fill with "1".
- Sparse: Mostly . – Backtrack fills systematically.
Final Thoughts
The Backtracking with Hash Sets solution is a powerhouse for LeetCode 37 in Python—clear, effective, and fun to implement. For a related challenge, try LeetCode 36: Valid Sudoku to warm up with validation! Ready to solve some puzzles? Solve LeetCode 37 on LeetCode now and test it with sparse or tricky boards to master backtracking. Dive in and crack the grid!