第73课 - 数独变体与剪枝

学习目标

完成本课学习后，你将能够：

理解传统回溯法在解决复杂数独变体时的性能瓶颈。
掌握“约束传播”这一高级剪枝思想的核心逻辑。
实现并应用“弧一致性”算法来显著提升数独求解器的效率。
识别不同数独变体中的关键约束，并据此调整算法。

核心概念

在上一课《全排列与组合》中，我们学习了用回溯法解决搜索问题。一个经典的回溯应用是求解标准9x9数独。但当我们遇到规则更复杂的数独变体（例如“锯齿数独”）时，简单的回溯法会因搜索空间爆炸而变得异常缓慢。

关键问题：能否在深度搜索前，通过一些推理提前排除掉大量不可能的选择，从而“剪枝”？

1. 约束传播：这不仅是一种剪枝技术，更是一种思维方式。它的核心是：当确定一个格子的值后，不仅更新它所在的行、列、宫，还要检查所有受其影响的其他格子，根据新信息进一步推导出新的确定值或排除不可能的值。 这个过程就像多米诺骨牌，一处确定引发一连串的连锁反应，大幅缩小后续搜索空间。

2. 弧一致性：这是实现约束传播的一种具体算法。想象每个格子（变量）都与它的所有“邻居”（存在约束关系的其他格子）通过一条“弧”相连。保证“弧一致性”意味着，对于每条弧(A, B)，A的当前值域中的每一个值，在B的值域中都能找到一个与之兼容的值，反之亦然。通过不断调整变量的值域（移除不兼容的值），直到所有弧都一致，我们可以极大地简化问题。

3. 应用于数独变体：以“锯齿数独”为例，它的宫不再是规整的3x3方块，而是不规则形状。这意味着我们需要动态生成每个格子的“宫邻居”。约束传播和弧一致性的逻辑不变，但约束关系的检查需要依据新规则进行。

代码示例：带约束传播的数独求解器

以下代码展示了一个从暴力回溯到加入约束传播的演进示例。我们将实现一个能处理不规则宫（锯齿数独）的求解器。

import copy

def is_valid(board, row, col, num, irregular_cages=None):
    """
    检查在(row, col)处放置num是否合法。
    irregular_cages: 字典，键为格子坐标元组，值为其所属的宫ID。为None时视为标准数独。
    """
    # 检查行
    for j in range(9):
        if board[row][j] == num:
            return False
    
    # 检查列
    for i in range(9):
        if board[i][col] == num:
            return False
    
    # 检查宫
    if irregular_cages:
        cage_id = irregular_cages[(row, col)]
        # 查找同宫所有格子
        for (i, j), cid in irregular_cages.items():
            if cid == cage_id and board[i][j] == num:
                return False
    else:
        # 标准3x3宫
        start_row, start_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(3):
            for j in range(3):
                if board[start_row + i][start_col + j] == num:
                    return False
    return True

def get_possible_values(board, row, col, irregular_cages=None):
    """获取某个格子当前所有可能的候选值。"""
    possible = []
    for num in range(1, 10):
        if is_valid(board, row, col, num, irregular_cages):
            possible.append(num)
    return possible

def find_empty_with_possibilities(board, irregular_cages=None):
    """找到值域最小的空格（MRV启发式，也是剪枝的一种策略）。"""
    min_possibilities = 10
    best_cell = None
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                possibles = get_possible_values(board, i, j, irregular_cages)
                if len(possibles) < min_possibilities:
                    min_possibilities = len(possibles)
                    best_cell = (i, j, possibles)
                    if min_possibilities == 1:  # 已经找到唯一可能的格子，直接返回
                        return best_cell
    return best_cell

def constraint_propagation(board, irregular_cages=None):
    """
    实现约束传播（简化版弧一致性）。
    核心逻辑：当一个格子的值被确定后，移除所有相关格子中这个值。
    如果某个格子的候选值变为空，则传播失败；如果某个格子的候选值唯一，则继续传播。
    """
    changed = True
    while changed:
        changed = False
        for i in range(9):
            for j in range(9):
                if board[i][j] != 0:
                    num = board[i][j]
                    # 移除行邻居的候选值
                    for k in range(9):
                        if k != j and board[i][k] == 0:
                            # 检查是否有效（仅演示逻辑，实际实现需维护候选表）
                            pass
                    # 移除列邻居的候选值
                    for k in range(9):
                        if k != i and board[k][j] == 0:
                            pass
                    # 移除宫邻居的候选值（需根据规则动态获取）
                    # 此处逻辑简化，实际实现较为复杂
    # 注意：一个完整的实现需要维护一个每个格子的候选值列表，并在传播中更新。
    # 这里为了突出算法骨架，省略了复杂的候选值维护细节。
    return board

def solve_sudoku(board, irregular_cages=None):
    """带启发式和约束传播剪枝的数独求解主函数。"""
    # 尝试进行约束传播预处理
    board = constraint_propagation(board, irregular_cages)
    
    # 使用MRV启发式寻找最佳空格
    cell = find_empty_with_possibilities(board, irregular_cages)
    if not cell:
        return True  # 没有空格，解决成功
    
    row, col, possibilities = cell
    
    # 尝试当前格子的每一个候选值
    for num in possibilities:
        # 模拟放置
        board[row][col] = num
        
        # 递归求解
        if solve_sudoku(board, irregular_cages):
            return True
        
        # 回溯
        board[row][col] = 0
    
    return False

# 测试：标准数独
standard_board = [
    [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]
]

if solve_sudoku(standard_board):
    print("标准数独求解成功！")
    for row in standard_board:
        print(row)
else:
    print("无解。")

# 关于“锯齿数独”的测试需要定义一个不规则宫的映射字典，此处省略。
# irregular_cages_example = {
#     (0,0): 'A', (0,1): 'A', (1,0): 'A', (1,1): 'B', (1,2): 'B', ... 
# }

实践练习

练习1：基础约束传播

题目：假设一个简化的4x4数独（1-4），宫为2x2。你已知第0行第0列确定为1。请手动列出，在应用一次行、列、宫约束传播后，与(0,0)相关的其他格子（(0,1), (0,2), (0,3), (1,0), (2,0), (1,1)）的候选值发生了什么变化。
要求：以列表形式写出变化前后的候选值。
预期输出示例：(0,1): [2,3,4] -> [2,3,4] (无变化)，(1,0): [2,3,4] -> [2,3,4]。

练习2：实现不规则宫检查

题目：完善示例代码中的is_valid函数对irregular_cages参数的处理。确保它能根据给定的宫ID映射字典，正确判断一个数字是否与同宫内的其他数字冲突。
要求：写出is_valid函数中检查不规则宫的完整代码片段。
预期输出：当irregular_cages非空时，能正确使用它进行宫内冲突检查。

练习3：算法比较与分析

题目：分别用“纯回溯”和“带约束传播（及MRV）的回溯”两种算法，求解同一个中等难度的数独题目（可以自行构造或使用题库）。记录并比较两者的递归调用次数。
要求：在代码中添加计数器，打印出两种算法完成求解所需的递归调用次数。
预期输出：一个数字对比，例如“纯回溯: 15234 次 vs 约束传播: 421 次”。

常见错误

忽略约束传播的时机：约束传播应该在每次做出决策（放置一个数字）后立即进行，并可能引发连锁反应。仅在最开始做一次预处理是不够的。
处理变体规则时遗漏约束：在实现如“锯齿数独”时，最容易忘记更新所有需要检查宫的地方（不仅仅是is_valid，还有get_possible_values等函数）。宫规则的判断需要贯穿整个求解逻辑。
算法实现错误导致死循环：在实现弧一致性时，如果没有妥善处理值域变化的传播条件和终止条件，可能导致无限循环。务必确保每一步移除候选值都是基于新信息，并且有明确的结束标志。
混淆约束传播与回溯：约束传播是一种前向检查和推理技术，它发生在回溯的递归调用之前。它的目的是简化当前状态，而不是替代回溯决策。

小结

从暴力到智能：高级数独变体迫使我们从简单的“试错”升级为“先推理，再试错”。约束传播是这种推理的核心。
剪枝的本质：在搜索过程中，尽早地发现并排除无效分支。弧一致性通过维护变量间的一致性关系，系统性地实现剪枝。
算法的适应性：解决一个通用问题（如数独）的算法框架是稳定的，但其关键部分（如约束关系的定义）需要根据具体问题（不同的数独规则）进行定制。irregular_cages参数的引入体现了这种设计思想。
性能飞跃：虽然实现起来更复杂，但引入约束传播和启发式（如MRV）后的求解器，其性能提升通常是指数级的，是解决大规模约束满足问题的必备技能。

掌握这些技巧后，你将能够更优雅、高效地应对各类复杂的搜索与优化问题。

练习编辑器

rust