Python高效解Pentomino：位图与启发式搜索技巧

Pentomino拼图（五格骨牌）是一种经典的组合谜题，目标是将12种不同形状的五格骨牌（每种由五个正方形组成）无缝地填入一个矩形区域。对于一个5x12的矩形，理论上存在1010种独特的解决方案。然而，使用朴素的回溯算法来寻找所有解，往往会面临巨大的性能挑战。例如，一个简单的Python实现可能需要20多秒才能找到一个解，这意味着要找到所有解可能需要数小时甚至更长时间，这在实际应用中是不可接受的。

核心挑战：朴素回溯法的性能瓶颈

最初的Pentomino求解器通常采用基于坐标的回溯算法。其基本流程是在棋盘上逐个尝试放置拼图块，如果当前位置无法放置，则回溯到上一个决策点。这种方法存在以下几个主要性能瓶颈：

1. 低效的棋盘与拼图表示： 使用二维字符数组表示棋盘，以及列表的列表表示拼图块，每次放置、移除或检查有效性都需要遍历坐标，这在大量操作下效率低下。
2. 动态的拼图变换： 在搜索过程中，每次尝试放置拼图块时，都需要动态生成其所有可能的旋转和翻转形态，这增加了大量的重复计算。
3. 盲目的搜索顺序： 朴素的回溯算法通常从棋盘的第一个空位开始尝试放置拼图，这种顺序可能导致在无效路径上浪费大量时间。
4. 昂贵的剪枝操作： 某些优化尝试，例如检查最小封闭区域是否小于拼图块大小，虽然可以剪枝，但其自身的计算成本可能非常高，反而拖慢了整体速度。

为了克服这些挑战，我们需要引入更高效的数据结构和搜索策略。

性能优化策略

以下是显著提升Pentomino求解器性能的关键策略：

1. 位图表示与操作

将棋盘和拼图块表示为位图（即单个大整数）是提升性能的核心。Python的原生大整数支持使得这种方法可行。通过位图，我们可以利用位运算（如AND, OR, XOR）来高效地执行拼图的放置、移除和碰撞检测。

• 棋盘表示： 整个棋盘可以被视为一个扁平化的二进制位串。为了模拟行之间的“墙壁”并简化位移操作，通常会在每行末尾添加一个额外的位。例如，对于一个宽度为W的棋盘，每行将占据W+1位，其中第W+1位始终为1，表示边界。
• 拼图块表示： 每个拼图块的特定形态和位置也可以表示为一个位图。当拼图块放置在棋盘上时，其位图与棋盘位图进行位或操作（board | piece_bitmap）即可完成放置；检查冲突则通过位与操作（board & piece_bitmap）判断是否为0。

2. 预计算所有拼图变换

与其在搜索过程中动态旋转和翻转拼图块，不如在搜索开始前，预先生成每种拼图块的所有可能形态（包括旋转和翻转）及其在棋盘上所有有效的位置，并将其转换为位图存储起来。

• 生成变换： 对于每个原始拼图块，生成其所有独特的旋转（90度、180度、270度）和翻转（水平翻转）形态。
• 位图化与预移位： 将每种形态转换为位图，并针对棋盘的每个可能起始位置进行位移，生成该形态在棋盘上所有不与边界重叠的有效位图表示。这些预计算的位图将作为搜索时的“可用动作”列表。

3. 智能选择下一个放置点：最少可能性启发式

传统的深度优先搜索（DFS）通常从棋盘的第一个空位开始尝试放置。然而，更高效的策略是采用“最少可能性优先”启发式（Minimum Remaining Values, MRV），也称为“最受约束变量优先”。

• 启发式原理： 在每一步搜索中，不选择第一个空位，而是选择棋盘上“最难被覆盖”的空位。这个“最难”通常指能覆盖该空位的拼图块种类或形态最少。如果一个空位只有很少的拼图块能覆盖它，那么我们应该优先处理它。如果这个空位最终无法被覆盖，算法就能更快地发现死胡同并回溯，从而显著剪枝。
• 实现方式： 遍历棋盘的每一行，找到第一个空位。对于这些空位，计算有多少种拼图块（及其变换形态）能够覆盖它。选择那个拥有最少覆盖可能性的空位，并只尝试用这些有限的拼图块来覆盖它。

4. 移除昂贵的剪枝操作

当采用了“最少可能性启发式”后，原先的“寻找最小封闭区域”等昂贵剪枝操作就可以被移除。因为“最少可能性启发式”本身就具有很强的剪枝能力：如果一个空位无法被任何拼图块覆盖，那么在选择该空位时，其可能性计数将为零，导致立即回溯。这种“失败早发现”的机制比复杂区域检查更高效。

5. 延迟结果表示

只有在找到一个完整的解决方案时，才将位图形式的棋盘转换回人类可读的字符矩阵。在搜索过程中，所有操作都应保持在位图层面，避免不必要的字符串或列表操作。

优化后的求解器实现

以下是结合上述优化策略的Python Pentomino求解器代码。请注意，拼图块的定义格式已更改为更易于转换为位图的二维字符串元组表示。

import datetime

def solve(height, width, pieces):
    """
    高效求解Pentomino拼图的所有解。
    :param height: 棋盘高度
    :param width: 棋盘宽度
    :param pieces: 拼图块字典，键为名称，值为二维字符串元组表示的形状
    :return: 打印所有解决方案
    """

    def rotate(piece):
        """旋转拼图块90度"""
        # 创建一个新列表，用于存储旋转后的行
        lst = [""] * len(piece[0])
        # 遍历原始拼图的每一行
        for line in piece:
            # 遍历当前行的每个字符及其索引
            for j, ch in enumerate(line):
                # 将字符添加到新列表的对应索引位置
                lst[j] += ch
        # 反转列表，得到最终旋转结果
        return tuple(reversed(lst))

    def flip(piece):
        """水平翻转拼图块"""
        return tuple(reversed(piece))

    def all_transformations(piece):
        """获取一个拼图块的所有独特旋转和翻转形态"""
        transfos = [piece]
        # 生成旋转形态
        while len(transfos) < 4: # 最多4种旋转形态
            new_piece = rotate(transfos[-1])
            if new_piece == piece: # 旋转回原形，停止
                break
            transfos.append(new_piece)

        # 生成翻转形态，并与现有形态合并去重
        flipped_transfos = list(map(flip, transfos))
        # 使用set去重，因为有些拼图块翻转后与旋转形态相同
        return set(transfos + flipped_transfos)

    def piece_to_bitmap(piece):
        """将二维字符串表示的拼图块转换为位图"""
        bitmap = 0
        for line in piece:
            # 每行末尾添加一个额外的位作为“墙壁”，然后左移并合并
            bitmap = (bitmap << (width + 1)) | int(line, 2)
        return bitmap

    def create_piece_bitmaps(piece_name, piece_shape):
        """
        为给定拼图块生成所有可能的位图形式（包括所有变换和在棋盘上的所有有效位置）。
        """
        bitmaps = []
        # 遍历所有变换形态
        for transformed_piece in all_transformations(piece_shape):
            # 将形态转换为基础位图
            base_bitmap = piece_to_bitmap(transformed_piece)

            # 遍历棋盘上的所有可能起始位置（通过位移实现）
            # 初始位图可能在棋盘的左上角，通过不断左移来模拟在棋盘上移动
            current_bitmap = base_bitmap
            # 循环直到位图移出棋盘范围
            while current_bitmap < (1 << (height * (width + 1))): # 棋盘总位数
                # 检查位图是否与棋盘的“墙壁”部分重叠 (即跨行)
                # 如果 (current_bitmap & board_wall_mask) != 0 则表示跨行
                # 这里的 board 是一个全1的掩码，用于判断是否越界或与“墙壁”重叠
                # 优化后的判断：只需确保不与棋盘边界（虚拟墙）重叠
                # 棋盘的初始 board 定义已经包含了墙壁，所以这里只需要检查是否与当前 board 冲突

                # 检查拼图块是否越界或与棋盘的“墙壁”重叠
                # piece_to_bitmap 已经包含了墙壁位，所以这里直接检查是否超出总棋盘范围
                # 并且不与棋盘初始边界（所有1位）冲突

                # 这里的逻辑是：如果当前位图与一个表示整个棋盘的位图（包含墙壁）进行AND操作后为0，
                # 并且不与已经放置的拼图块重叠（通过与当前棋盘状态的AND操作判断），则它是有效的。
                # 在 create_piece_bitmaps 阶段，我们只生成所有可能的放置位置，不考虑当前棋盘状态。
                # 这里的 `board` 实际上是 `board_boundary_mask`，表示棋盘的有效区域和墙壁。
                # 拼图块不能与墙壁重叠，也不能超出棋盘边界。

                # 更准确的边界检查：
                # 1. 拼图块不能超出右边界 (通过检查每一行是否跨越了宽度W)
                # 2. 拼图块不能超出下边界 (通过检查是否移出了整个棋盘的高度H)

                # 简化检查：我们预先构建的 `board_boundary_mask` 包含了墙壁。
                # 只要 piece_to_bitmap 产生的位图与 `board_boundary_mask` 没有交集，就意味着它没有与墙壁重叠。
                # 并且，它不能移出 `board_boundary_mask` 的范围。

                # 这里的 `board` 在 create_piece_bitmaps 外部定义，表示整个空的棋盘（包含墙壁位）。
                # `(current_bitmap & board) == 0` 这个条件是检查拼图块是否与棋盘的“墙壁”重叠。
                # 这里的 `board` 实际上是一个全1的掩码，代表了棋盘的有效区域和墙壁。
                # 如果拼图块的任何一个1位落在了棋盘的“墙壁”位上，则 `(current_bitmap & board)` 将不为0。
                # 但更准确的说法是：`board` 应该是一个表示棋盘边界的位图，初始为空棋盘时，它只包含墙壁位。
                # `(bitmap & board)` 检查的是拼图块是否与已放置的拼图块重叠，或者是否与棋盘边界（墙壁）重叠。
                # 在预处理阶段，我们只关心它是否与墙壁重叠。

                # 这里的 `board` 变量名有点误导，它实际上是 `initial_empty_board_mask`
                # 确保拼图块没有与墙壁重叠，且没有超出右边界。
                # 一个简单的方法是：如果 (current_bitmap & board_boundary_mask) == 0
                # 且 current_bitmap 的最右边1位没有超出宽度W的限制。

                # 修正：这里的 `board` 应该是表示棋盘边界的位图，用于检查拼图块是否越界或与墙壁重叠。
                # 原始代码中的 `board` 在 `solve` 函数外部定义为 `board = 1 << width ...`，
                # 它是一个掩码，其中所有墙壁位是1，所有可放置的空位是0。
                # 因此，`(bitmap & board) == 0` 意味着拼图块没有与任何墙壁重叠。
                # 并且 `bitmap < (1 << (height * (width + 1)))` 确保它在整个棋盘范围内。
                if (current_bitmap & board) == 0:  # 检查是否与“墙壁”重叠 (board 此时是墙壁掩码)
                    bitmaps.append(current_bitmap)

                # 检查是否即将跨越棋盘右边界（即进入下一行的墙壁位）
                # 如果当前位图的任何一个1位在当前行的宽度W之外（即在墙壁位上），则该位图无效。
                # 这个检查已经在 `(current_bitmap & board) == 0` 中隐含了。

                # 移动到下一个可能的位置（右移一位）
                current_bitmap <<= 1
        return bitmaps

    def get_candidates(current_board, piece_bitmaps):
        """
        根据“最少可能性”启发式，选择下一个要放置拼图块的空位，并返回能覆盖该空位的拼图块列表。
        :param current_board: 当前棋盘状态的位图
        :param piece_bitmaps: 剩余拼图块及其所有位图表示的字典
        :return: 列表，包含 (piece_key, piece_bitmap) 对，表示能覆盖“最难”空位的拼图块
        """
        least_fillers = []
        least = float('inf') # 最小可能性数量

        # rowmask 用于逐行扫描，每次移动到下一行时，它会跳过墙壁位
        # (1 << (width + 1)) - 1 是一个掩码，表示一行（包括墙壁）的所有位都是1
        rowmask = (1 << (width + 1)) - 1 

        for _ in range(height): # 遍历每一行
            # 找到当前行的空闲位：
            # (current_board & rowmask) 得到当前行已占用的位
            # ^ rowmask 对其取反，得到当前行的空闲位 (1表示空闲，0表示占用或墙壁)
            bitrow = (current_board & rowmask) ^ rowmask  
            rowmask <<= width + 1  # 移动到下一行的掩码

            if not bitrow:  # 如果当前行完全被占用，则跳过
                continue

            # cell 找到当前行最左边的空闲位 (最低位的1)
            cell = bitrow & -bitrow  # 等价于 bitrow & (~bitrow + 1)

            # 检查哪些剩余的拼图块可以覆盖这个 `cell`
            fillers = []
            for key, bitmaps in piece_bitmaps.items():
                for bitmap in bitmaps:
                    # 1. `cell & bitmap`: 确保拼图块的某个位覆盖了 `cell`
                    # 2. `(bitmap & current_board) == 0`: 确保拼图块不会与棋盘上已放置的拼图块重叠
                    if (cell & bitmap) and (bitmap & current_board) == 0:
                        fillers.append((key, bitmap))
                        # 提前剪枝：如果当前空位的可能性已经超过了已知最小可能性，则无需继续检查
                        if len(fillers) >= least: 
                            break # 跳出内层循环 (遍历