import itertools
from collections import defaultdict
# 初始盤面 (0 為空)
board = [
[0,7,0, 0,0,0, 0,0,0],
[5,0,3, 0,0,6, 0,0,0],
[0,6,2, 0,8,0, 7,0,0],
[0,0,4, 0,1,0, 3,0,0],
[0,2,0, 9,0,5, 0,0,0],
[0,0,1, 0,3,0, 5,9,0],
[0,0,0, 4,0,0, 6,0,3],
[0,0,0, 0,0,0, 0,2,0],
]
# 所有 1-9 全排列
ALL_PERMS = list(itertools.permutations(range(1,10), 9))
# 既有數字位置
fixed = {(r,c):v for r,row in enumerate(board) for c,v in enumerate(row) if v}
# 行約束:每行已知數字 {col: val}
row_constraints = defaultdict(dict)
# 列約束:每列已知數字 {row: val}
col_constraints = defaultdict(dict)
for (r,c), v in fixed.items():
row_constraints[r][c] = v
col_constraints[c][r] = v
# 篩選各行候選排列
row_candidates = {}
for r in range(9):
rc = row_constraints[r]
candidates = [p for p in ALL_PERMS if all(p[c]==v for c,v in rc.items())]
# 列約束進一步篩選
candidates = [p for p in candidates if all(p[c] != col_constraints[c].get(r) for c in range(9) if r in col_constraints[c])]
row_candidates[r] = candidates
def check_3x3(grid, r, c, val):
"""檢查 (r,c) 放 val 是否衝突 3x3 宮"""
br, bc = (r//3)*3, (c//3)*3
for i in range(br, br+3):
for j in range(bc, bc+3):
if (i,j) != (r,c) and grid[i][j] == val:
return False
return True
solutions = []
grid = [[0]*9 for _ in range(9)]
def backtrack(row=0):
if row == 9:
solutions.append([row[:] for row in grid])
return
for perm in row_candidates[row]:
# 檢查列衝突
if any(grid[r][c] == perm[c] for r in range(row) for c in range(9)):
continue
# 檢查 3x3 宮衝突 (僅檢查已填行)
ok = True
for c in range(9):
if not check_3x3(grid, row, c, perm[c]):
ok = False
break
if not ok:
continue
# 放置
grid[row] = list(perm)
backtrack(row+1)
# 回溯
grid[row] = [0]*9
backtrack()
print(f"找到 {len(solutions)} 組解")
for sol in solutions:
for row in sol:
print(row)
print("---")
python-constraint 或 ortools CP-SAT 求解器展示 Python itertools.permutations、defaultdict、列表推導、回溯遞迴、剪枝策略等核心技巧綜合應用。