Python 0037.py
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def simplify(solution):
changes = 0
for x in range(9):
for y in range(9):
# solved cell
if len(solution[x][y]) == 1:
continue
avoid = set()
for i in range(9):
# same column
if len(solution[x][i]) == 1:
avoid.add(solution[x][i][0])
# same row
if len(solution[i][y]) == 1:
avoid.add(solution[i][y][0])
# same box
xx = (x // 3) * 3 + i % 3
yy = (y // 3) * 3 + i // 3
if len(solution[xx][yy]) == 1:
avoid.add(solution[xx][yy][0])
for a in avoid:
if a in solution[x][y]:
solution[x][y].remove(a)
changes += 1
if len(solution[x][y]) == 0:
return -1
return changes
def validate(solution): # only checks if one candidate per cell, no further validation
for x in range(9):
for y in range(9):
if len(solution[x][y]) > 1:
return False
me = solution[x][y][0]
for i in range(9):
if i != x and me == solution[i][y][0]:
return False
if i != y and me == solution[x][i][0]:
return False
xx = (x // 3) * 3 + i % 3
yy = (y // 3) * 3 + i // 3
if (x != xx or y != yy) and me == solution[xx][yy][0]:
return False
return True
def isFinished(solution): # only checks if one candidate per cell, no further validation
for x in range(9):
for y in range(9):
if len(solution[x][y]) > 1:
return False
return True
def solve(deeper):
# deep copy (why so weird in Python ?)
attempt = []
for x in range(9):
r = []
for y in range(9):
r.append(deeper[x][y].copy())
attempt.append(r)
if simplify(attempt) < 0:
return None
if isFinished(attempt):
return attempt if validate(attempt) else None
for x in range(9):
for y in range(9):
if len(deeper[x][y]) > 1:
guess = deeper[x][y]
for c in guess:
attempt[x][y] = [ c ]
complete = solve(attempt)
if complete != None:
return complete
return None
return attempt
# 9 strings, each 9 bytes
candidates = []
for row in board:
r = []
for cell in row:
if cell == ".":
r.append([ 1,2,3,4,5,6,7,8,9 ])
else:
r.append([ int(cell) ])
candidates.append(r)
s = simplify(candidates)
while s > 0:
s = simplify(candidates)
# let's go
final = solve(candidates)
# convert to Leetcode format
result = []
for x in range(9):
r = []
for y in range(9):
board[x][y] = str(final[x][y][0])
Difficulty
and has an acceptance rate of about 66% (1+ million submissions).
Typical patterns to solve this problem:
- Array
- Backtracking
- Hash Table
- Matrix
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The implementation solves a standard 9×9 Sudoku puzzle by maintaining, for every cell, a list of possible digits. The algorithm proceeds in three phases:
- Candidate construction - each empty cell receives the full digit set {1…9}, while pre-filled cells receive a singleton list.
- Constraint propagation - the
simplifyroutine repeatedly removes digits that are already fixed in the same row, column, or 3×3 box. - Depth-first search with backtracking - when propagation cannot finish the board, the solver guesses a candidate, recurses, and restores state on failure.
All modifications are performed on the supplied board in-place, satisfying the LeetCode contract.
Candidate Initialization
The board is scanned once to build a parallel structure candidates. For a dot (".") the full range 1-9 is stored; otherwise the digit is converted to an integer and wrapped in a list.
candidates = []
for row in board:
r = []
for cell in row:
if cell == ".":
r.append([1,2,3,4,5,6,7,8,9])
else:
r.append([int(cell)])
candidates.append(r)
This step guarantees that every cell has at least one possible value, establishing a well-defined starting point for the solver.
Constraint Propagation (simplify)
simplify iterates over every cell, collecting digits that are already resolved in the same row, column, and box into a set avoid. Those digits are then removed from the current cell’s candidate list. The function returns the total number of eliminations performed, or -1 if a cell loses all candidates, signalling an immediate contradiction.
def simplify(solution):
changes = 0
for x in range(9):
for y in range(9):
if len(solution[x][y]) == 1:
continue
avoid = set()
for i in range(9):
if len(solution[x][i]) == 1:
avoid.add(solution[x][i][0])
if len(solution[i][y]) == 1:
avoid.add(solution[i][y][0])
xx = (x // 3) * 3 + i % 3
yy = (y // 3) * 3 + i // 3
if len(solution[xx][yy]) == 1:
avoid.add(solution[xx][yy][0])
for a in avoid:
if a in solution[x][y]:
solution[x][y].remove(a)
changes += 1
if len(solution[x][y]) == 0:
return -1
return changes
Edge Cases Handled
- Cells that are already solved are skipped, preventing unnecessary work.
- The use of a set eliminates duplicate checks when a digit appears in multiple intersecting constraints.
- Returning
-1when a candidate list becomes empty captures an impossible configuration early, allowing the caller to backtrack without further recursion.
Validation (validate)
After a full assignment is reached, validate confirms that each digit appears exactly once in its row, column, and box. It assumes every cell holds a singleton list, so the check is a simple equality comparison.
def validate(solution):
for x in range(9):
for y in range(9):
if len(solution[x][y]) > 1:
return False
me = solution[x][y][0]
for i in range(9):
if i != x and me == solution[i][y][0]:
return False
if i != y and me == solution[x][i][0]:
return False
xx = (x // 3) * 3 + i % 3
yy = (y // 3) * 3 + i // 3
if (x != xx or y != yy) and me == solution[xx][yy][0]:
return False
return True
The function gracefully handles the case where a cell still contains multiple candidates by returning False immediately, preventing false positives.
Completion Check (isFinished)
isFinished determines whether every cell has been reduced to a single candidate, serving as a fast termination test before invoking the more expensive validate.
def isFinished(solution):
for x in range(9):
for y in range(9):
if len(solution[x][y]) > 1:
return False
return True
Recursive Solver (solve)
The core search routine creates a deep copy of the current candidate grid, applies simplify, and then decides the next action:
- If propagation yields a contradiction (
simplify< 0), the branch is abandoned. - If the board is finished,
validatedecides whether the solution is legal. - Otherwise, the algorithm selects the first cell with multiple candidates, iterates over its possibilities, forces each guess, and recurses.
def solve(deeper):
attempt = []
for x in range(9):
r = []
for y in range(9):
r.append(deeper[x][y].copy())
attempt.append(r)
if simplify(attempt) < 0:
return None
if isFinished(attempt):
return attempt if validate(attempt) else None
for x in range(9):
for y in range(9):
if len(deeper[x][y]) > 1:
guess = deeper[x][y]
for c in guess:
attempt[x][y] = [c]
complete = solve(attempt)
if complete != None:
return complete
return None
return attempt
Edge Cases Handled
- The deep copy isolates each recursive branch, ensuring that guesses do not corrupt sibling branches.
- The early return after trying all candidates for a cell prevents unnecessary exploration of other cells when the current branch is already invalid.
- The final
return attemptacts as a safety net for the unlikely case where the loop finishes without finding a multi-candidate cell, returning the partially solved grid.
Iterative Simplification Loop
Before invoking the recursive search, the solver repeatedly calls simplify until no further reductions occur. This maximizes deterministic deductions and reduces the depth of the subsequent search.
s = simplify(candidates)
while s > 0:
s = simplify(candidates)
The loop stops when simplify reports zero changes, indicating that constraint propagation has reached a fixed point.
Final Board Conversion
When a complete candidate grid is obtained, the solver writes the solved digits back into the original board as strings, matching the expected output format.
final = solve(candidates)
for x in range(9):
for y in range(9):
board[x][y] = str(final[x][y][0])
Because final is guaranteed to contain a single digit per cell, the conversion is straightforward and safe.
Performance Optimizations
- Set-based avoidance - using a Python
setto collect digits already placed in intersecting units avoids repeated linear scans and duplicate work. - Early contradiction detection -
simplifyaborts as soon as a cell loses all candidates, preventing deeper recursion on an impossible branch. - Fixed-point propagation - the outer loop runs
simplifyonly while it makes progress, eliminating redundant passes once the board is stable. - Targeted deep copy - the copy operation replicates only the candidate lists, not the entire board, keeping memory overhead modest while preserving isolation between recursive calls.
- First-unsolved-cell heuristic - by selecting the first cell with multiple candidates, the solver avoids the overhead of scanning for the minimal-size candidate set, which in practice yields acceptable performance on typical puzzles.
These choices collectively keep the solver responsive for standard Sudoku instances while maintaining clear, readable code.
ELI5 - Simplified Explanation
Imagine playing a big puzzle game where you have a square grid filled with empty boxes. This code is like a smart friend helping you play Sudoku. To start, this friend looks at the grid and writes down every number from one to nine in the empty boxes because any of those numbers might work. If a box already has a number, the friend just keeps that one.
After writing down all the possibilities, the friend starts following the three special rules of Sudoku. The friend checks every row, every column, and every little square group to see which numbers are already taken. Whenever a number is found in a row or column, the friend crosses it out from the options in the other empty boxes. This makes the list of possibilities smaller and clearer.
Sometimes, after crossing out numbers, only one option is left for a box. When that happens, the friend knows that number must go there. This keeps happening over and over until many boxes are solved.
If the board still has boxes with more than one option and no more simple moves are left, the friend takes a little risk. The friend picks a box with a few choices, guesses one, and sees if the rest of the puzzle stays correct. If the guess leads to a mistake, the friend goes back and tries a different choice. The friend keeps guessing and checking until every single box is filled with the right number, which finishes the whole game.
Code Quality
Complexity Analysis
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||||||
| WalkCCC | C++ | Python | Java | |||||||||
| leetcode.ca | C++ | Python | C# | Java | Go | PHP | ||||||
| LeetcodeHelp | C++ | Python | Java | |||||||||
| MemoryLimitExceeded | C++ | Python | ||||||||||
| Progiez | C++ | Python | Java | |||||||||
| github | aylei | Rust | ||||||||||
| begeekmyfriend | C | |||||||||||
| BigEggStudy | C# | |||||||||||
| black-shadows | Python | |||||||||||
| charles-wangkai | Java | |||||||||||
| chenyanzhe | C++ | |||||||||||
| everthis | JS | |||||||||||
| gaosq0604 | Python | |||||||||||
| halfrost | Go | |||||||||||
| haoel | C++ | |||||||||||
| JoshCrozier | JS | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| lennylxx | C++ | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| luangong | C++ | |||||||||||
| MacJim | C++ | |||||||||||
| martianoff | Scala | |||||||||||
| qiyuangong | Python | |||||||||||
| ruoru | Rust | |||||||||||
| shreymehul | C# | |||||||||||
| suxrobGM | C# | |||||||||||
| vli02 | C | |||||||||||
| wisdompeak | C++ | |||||||||||
| XiaotaoGuo | C++ | |||||||||||
| zfang399 | C++ | |||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||||
| WalkCCC | C++, Python, Java | |||||||||||
| leetcode.ca | C++, C#, Go, Java, PHP, Python | |||||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||||
| MemoryLimitExceeded | Python, C++ | |||||||||||
| Progiez | C++, Java, Python | |||||||||||
| aylei | Rust | |||||||||||
| begeekmyfriend | C | |||||||||||
| BigEggStudy | C# | |||||||||||
| black-shadows | Python, Python | |||||||||||
| charles-wangkai | Java | |||||||||||
| chenyanzhe | C++ | |||||||||||
| everthis | JavaScript | |||||||||||
| gaosq0604 | Python | |||||||||||
| halfrost | Go | |||||||||||
| haoel | C++ | |||||||||||
| JoshCrozier | JavaScript | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| lennylxx | C++ | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| luangong | C++ | |||||||||||
| MacJim | C++ | |||||||||||
| martianoff | Scala | |||||||||||
| qiyuangong | Python | |||||||||||
| ruoru | Rust | |||||||||||
| shreymehul | C# | |||||||||||
| suxrobGM | C# | |||||||||||
| vli02 | C | |||||||||||
| wisdompeak | C++ | |||||||||||
| XiaotaoGuo | C++ | |||||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 36: Valid Sudoku
Solved On The Same Day
- problem 110: Balanced Binary Tree
- problem 111: Minimum Depth of Binary Tree
- problem 118: Pascal's Triangle
- problem 119: Pascal's Triangle II
- problem 228: Summary Ranges
- problem 530: Minimum Absolute Difference in BST
- problem 82: Remove Duplicates from Sorted List II
- problem 102: Binary Tree Level Order Traversal
- problem 103: Binary Tree Zigzag Level Order Traversal
- problem 105: Construct Binary Tree from Preorder and Inorder Traversal
- problem 106: Construct Binary Tree from Inorder and Postorder Traversal
- problem 107: Binary Tree Level Order Traversal II
- problem 109: Convert Sorted List to Binary Search Tree
- problem 117: Populating Next Right Pointers in Each Node II
- problem 128: Longest Consecutive Sequence
- problem 138: Copy List with Random Pointer
- problem 150: Evaluate Reverse Polish Notation
- problem 155: Min Stack
- problem 209: Minimum Size Subarray Sum
- problem 274: H-Index
- problem 380: Insert Delete GetRandom O(1)
- problem 427: Construct Quad Tree
- problem 452: Minimum Number of Arrows to Burst Balloons
- problem 30: Substring with Concatenation of All Words
- problem 44: Wildcard Matching
- problem 1326: Minimum Number of Taps to Open to Water a Garden
Fun Facts
This is my longest hard solution with 4033 bytes.
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality