第 71 课 - 数独求解
所属模块：回溯与搜索
难度：Intermediate
标签：sudoku、constraint、propagate
上一课：N 皇后问题
下一课：全排列与组合
1. 学习目标
完成本课学习后，你将能够：
- 理解数独问题的核心规则与约束条件。
- 掌握使用回溯算法解决数独问题的基本思路。
- 学会利用“约束传播”（Constraint Propagation）来优化求解过程。
- 实现一个完整的、能解决标准 9x9 数独的 Python 求解器。
- 分析不同求解策略的优缺点与适用场景。
2. 核心概念
数独的规则：一个 9x9 的盘面，被划分为 9 个 3x3 的宫。规则是：在每一行、每一列以及每一个宫内，数字 1-9 都必须出现且仅出现一次。
回溯算法：回溯是解决数独的经典方法。想象你在玩数独，你会不断在空白格里尝试填入合法的数字（1-9），如果填入后发现违反了规则（比如与同行的数字冲突），就“回溯”到上一步，尝试另一个数字。这个过程就像在搜索一棵巨大的可能性树，遇到死路就返回。
约束传播：纯回溯可能会很慢，因为可能性太多。约束传播是一种优化思想：当我们确定一个格子填某个数字时，可以立刻更新其同行、同列、同宫其他格子的“可能值集合”（去除这个数字）。这能大幅减少后续需要尝试的数字数量，有时甚至能直接推出某些空格的唯一解。
盘面表示：我们需要一种数据结构来记录当前状态。通常使用一个 9x9 的二维列表（矩阵）：
0表示空格。1-9表示已确定的数字。
我们还会维护一个 9x9 的矩阵 possibles，其中每个元素是一个集合，存储该格子当前所有可能的数字。
3. 代码示例
下面是一个结合了回溯与约束传播的数独求解器。它首先尝试使用约束传播来简化盘面，如果仍有空格，则对第一个空格进行回溯尝试。
from typing import List, Set, Tuple, Optional
def solve_sudoku(board: List[List[int]]) -> bool:
"""
使用回溯与约束传播解决数独。
Args:
board: 9x9 的列表，0 表示空格。
Returns:
True 表示成功解出，False 表示无解。
"""
n = 9
# 1. 初始化每个格子的可能值集合
possible = [[set(range(1, 10)) for _ in range(n)] for _ in range(n)]
# 2. 初始化约束传播：根据初始盘面更新可能值
for i in range(n):
for j in range(n):
if board[i][j] != 0:
val = board[i][j]
if not eliminate(possible, i, j, val):
return False # 初始盘面矛盾，无解
# 3. 主求解逻辑
return backtrack(board, possible)
def eliminate(possible: List[List[Set[int]]], i: int, j: int, val: int) -> bool:
"""
消除格子 (i, j) 的可能值 val，并更新其关联格子。
"""
# 如果 val 不在可能值中，说明冲突
if val not in possible[i][j]:
return False
# 从 (i, j) 的可能值中移除 val
possible[i][j].discard(val)
remaining = possible[i][j]
# 如果移除后，该格子只剩一个可能值，则进行“传播”
if len(remaining) == 1:
only_val = next(iter(remaining))
# 检查 (i, j) 关联的所有格子（同行、同列、同宫），移除 only_val
for (ni, nj) in get_peers(i, j):
if not eliminate(possible, ni, nj, only_val):
return False
# 如果移除后，该格子没有可能值了，说明矛盾
elif len(remaining) == 0:
return False
return True
def get_peers(i: int, j: int) -> List[Tuple[int, int]]:
"""获取格子 (i, j) 的所有关联格子（同行、同列、同宫，共20个）。"""
peers = set()
# 同行
for col in range(9):
if col != j:
peers.add((i, col))
# 同列
for row in range(9):
if row != i:
peers.add((row, j))
# 同宫
box_row, box_col = 3 * (i // 3), 3 * (j // 3)
for r in range(box_row, box_row + 3):
for c in range(box_col, box_col + 3):
if r != i or c != j:
peers.add((r, c))
return list(peers)
def backtrack(board: List[List[int]], possible: List[List[Set[int]]]) -> bool:
"""回溯求解函数。"""
# 找到第一个空格（可能值集合大小 > 1 的格子，或原盘面为空格的格子）
for i in range(9):
for j in range(9):
if board[i][j] == 0 and len(possible[i][j]) > 1:
# 尝试这个格子的每个可能值
for val in list(possible[i][j]):
# 深拷贝当前状态，以便回溯
new_possible = [[s.copy() for s in row] for row in possible]
new_board = [row[:] for row in board]
# 尝试填入 val
new_board[i][j] = val
if not eliminate(new_possible, i, j, val):
continue # 冲突，尝试下一个值
# 递归求解
if backtrack(new_board, new_possible):
# 如果成功，将结果复制回原 board
for r in range(9):
board[r] = new_board[r][:]
return True
# 所有可能值都失败，回溯
return False
# 没有找到需要尝试的空格，检查是否所有格子都填满
for i in range(9):
for j in range(9):
if board[i][j] == 0:
# 检查是否有唯一解已经由约束传播确定
if len(possible[i][j]) == 1:
board[i][j] = next(iter(possible[i][j]))
else:
return False # 还有空格无法确定，无解
return True
# 测试代码
if __name__ == "__main__":
# 一个经典的数独问题（0表示空格）
puzzle = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]
print("原始盘面：")
for row in puzzle:
print(row)
if solve_sudoku(puzzle):
print("\n求解成功！")
for row in puzzle:
print(row)
else:
print("\n此数独无解！")
代码说明：
eliminate函数是约束传播的核心。它不仅移除一个值，还会在某个格子的可能值减少到 1 个时，递归地“传播”这个约束。backtrack函数负责回溯搜索。它总是选择第一个“未确定”且“有多个可能值”的格子进行分支。- 代码首先尝试用约束传播简化盘面，如果无法完全解决，再进行回溯。这种结合策略效率很高。
4. 实践练习
练习 1（基础）：修改上面的代码，使其能处理并解决下面这个“困难”数独。这个数独初始数字更少，对算法是更好的测试。
hard_puzzle = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 3, 0, 8, 5],
[0, 0, 1, 0, 2, 0, 0, 0, 0],
[0, 0, 0, 5, 0, 7, 0, 0, 0],
[0, 0, 4, 0, 0, 0, 1, 0, 0],
[0, 9, 0, 0, 0, 0, 0, 0, 0],
[5, 0, 0, 0, 0, 0, 0, 7, 3],
[0, 0, 2, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 4, 0, 0, 0, 9]
]
要求：在程序中加载并求解它，打印出完整的解。 预期输出：应成功输出一个 9x9 的、每行每列每宫都是 1-9 的矩阵。
练习 2（进阶）：为求解器添加一个“难度评估”函数。规则如下：
- 统计初始盘面中已知数字的数量。
- 如果已知数字数量少于 25，则认为是“困难”难度。
- 如果已知数字数量在 25 到 35 之间，则认为是“中等”。
- 如果已知数字数量大于 35，则认为是“简单”。
要求：编写函数
estimate_difficulty(board)，并在求解hard_puzzle前后分别调用它。 预期输出：
初始难度：困难
最终解法：（打印出解）
练习 3（挑战）：修改算法，使其能检测一个数独是否有唯一解。
提示：在回溯过程中，如果找到一个解后，不立即返回，而是继续搜索，如果又找到另一个不同的解，则说明不唯一。
要求：编写函数 has_unique_solution(board)。用它测试 hard_puzzle 和一个你自己构造的有多解的盘面。
预期输出：
hard_puzzle 有唯一解：True
有多解的盘面有唯一解：False
5. 常见错误
- 忽略约束传播，导致效率极低：纯暴力回溯（不维护
possible矩阵，每次填数字时都暴力检查同行、列、宫）在困难数独上可能非常慢。约束传播是数独求解的关键优化。 - 盘面表示错误：使用字符串或错误的数据结构初始化盘面，导致索引出错。
- 约束传播不彻底：在
eliminate函数中，当某个格子的可能值减少到 1 个时，没有递归地去更新它的所有关联格子，导致传播链断裂。 - 回溯状态复制问题：在回溯尝试时，直接修改了当前状态而没有备份，导致回溯后无法恢复到尝试前的状态。必须使用深拷贝。
- 边界检查遗漏：在计算同宫关联格子时，
get_peers函数中的宫内循环写错，导致遗漏或重复某些格子。
6. 小结
- 数独问题是一个典型的约束满足问题，完美结合了逻辑推理与搜索。
- 回溯算法提供了系统的试错框架，是解决这类问题的基础。
- 约束传播（特别是当某个格子的可能值被缩减到 1 个时进行的“唯一值传播”）能极大地简化问题，甚至在很多简单数独中直接推导出解，而无需回溯。
- 实际求解器通常是回溯与约束传播的混合体。先尽力用约束传播缩小搜索空间，当传播无法继续时，再选择可能性最少的格子进行回溯（本课代码选择了第一个，更优策略是选择“可能性最小的”格子，即MRV启发式）。
- 理解并实现数独求解器，是掌握回溯算法和约束编程思想的一个绝佳实践。这些思想可以推广到其他问题，如数独变体、其他逻辑谜题，甚至人工智能中的规划问题。
练习编辑器
rust
Loading...