Sudoku 是經典的 Constraint Problem（約束問題）。
. 填入 1～9，使得：- 每一列（row）數字 1～9 各出現一次
- 每一行（column）數字 1～9 各出現一次
- 每一個 3×3 box（九宮格）數字 1～9 各出現一次
這種問題最典型、最有效的方法就是：
DFS（深度優先搜尋） + Backtracking（回溯）
🧠 1. 人類是怎麼解 Sudoku 的？
人解 Sudoku 的直覺其實就是：
- 找一個空格
- 試著填 1～9
- 看會不會違反 row/col/box 規則
- 若合法 → 繼續解下一格
- 若後面遇到死路 → 改填其他數字（回溯）
你會邊試邊擦 → 這就是 backtracking。
程式也完全一樣，只是做得更精準。
🧱 2.數據結構：用 set 即時追蹤每個 row/col/box 已用的數字
我們建立三個資料結構：
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
代表：
rows[r]：第 r 行有哪些數字已經用過cols[c]：第 c 列用過哪些boxes[b]：第 b 個 3×3 九宮格用過哪些
為什麼用 set？
- 查詢「某數字是否已存在」為 O(1)
- 移除、加入也都是 O(1)
使得整體速度遠比暴力掃描 row/col/box 快。
📦 3.怎麼知道一個格子屬於哪個 3×3 box？
九宮格編號長這樣：
0 1 2
3 4 5
6 7 8
一個格子 (r, c) 的 box ID 是：
(r // 3) * 3 + (c // 3)
簡單直覺：
- 每 3 行是一大區 → r//3
- 每 3 列是一大區 → c//3
🔍 4.先收集所有空格（empties），讓 DFS 只跑必要位置
empties = []
for r in range(9):
for c in range(9):
if board[r][c] == '.':
empties.append((r, c))
else:
... # 把已有數字加入 set
這樣 DFS 就直接按照 empties 的順序填空位，不用每次去掃整個 board。
🔁 5.DFS：填第 idx 個空格
核心遞迴：
def dfs(idx):
if idx == len(empties):
return True # 全部填完
當 idx == 空格數量，表示：
全部的 . 都填好了 → Sudoku 解完！
✏️ 6. 嘗試填 1～9，合法再進下一格
r, c = empties[idx]
b = box_id(r, c)
for v in "123456789":
if v not in rows[r] and v not in cols[c] and v not in boxes[b]:
# 嘗試填這個數字
board[r][c] = v
rows[r].add(v)
cols[c].add(v)
boxes[b].add(v)
if dfs(idx + 1):
return True
這段做的事情是：
- 確認
v是否在 row/col/box 都沒出現 - 若合法 → 暫時填入
- 「往下一格」繼續 DFS
🔙 7. 如果之後失敗，就回溯（撤銷）
board[r][c] = '.'
rows[r].remove(v)
cols[c].remove(v)
boxes[b].remove(v)
這就是程式版的 擦掉答案重新試
🧩 8. 完整程式碼（可直接跑 LeetCode）
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
# 建立 9*3 個 set，分別紀錄 row / col / box 已用數字
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
empties = [] # 記錄所有空的 '.'
# 給定row跟col告訴我他屬於第幾個box
def box_id(r, c):
return (r // 3) * 3 + (c // 3)
# 初始化：把原本的數字放進 set
for r in range(9):
for c in range(9):
if board[r][c] == '.':
# 紀錄空位置
empties.append((r, c))
else:
v = board[r][c] #撈值出來
rows[r].add(v) #紀錄該row有這個值
cols[c].add(v) #紀錄該col有這個值
boxes[box_id(r, c)].add(v) #紀錄該box有這個值
# DFS + 回溯
def dfs(idx):
if idx == len(empties):
return True # 全部填完！
# 撈出空位置的 r,c,b
r, c = empties[idx]
b = box_id(r, c)
# 嘗試填入1-9
for v in "123456789":
if (v not in rows[r] #同一row唯一
and v not in cols[c] #同一col唯一
and v not in boxes[b]): #同一box唯一
# 放入
board[r][c] = v
rows[r].add(v)
cols[c].add(v)
boxes[b].add(v)
# 往下一格
if dfs(idx + 1):
return True
# 往下一格若失敗則回溯（撤銷）
board[r][c] = '.'
rows[r].remove(v)
cols[c].remove(v)
boxes[b].remove(v)
return False # 這格無解，回到上一層
dfs(0)
