萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 實作數獨求解器:排列組合 + 回溯剪枝完整實作

解題思路

  1. 預先計算每行所有合法排列 (1-9 全排列 9! = 362,880 種)
  2. 依初始盤面約束篩選各行候選排列
  3. 逐行回溯嘗試,行間檢查列與 3x3 宮約束
  4. 提前剪枝:若某列或宮出現重複數字即回溯

核心資料結構


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

回溯搜尋 (含 3x3 宮檢查)


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("---")

效能優化方向

  • 用位元組遮罩 (bitmask) 替代集合/列表檢查
  • 採用 DLX (Dancing Links) 精確覆蓋演算法
  • 引入啟發式:優先填候選最少的行/格 (MRV)
  • 使用 python-constraint 或 ortools CP-SAT 求解器

教學價值

展示 Python itertools.permutations、defaultdict、列表推導、回溯遞迴、剪枝策略等核心技巧綜合應用。

copyright © 萬盛學電腦網 all rights reserved