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 # 跳出内层循环 (遍历