Python五格拼板优化解法：位运算与回溯技巧

怎么入门文章编程？需要学习哪些知识点？这是新手们刚接触编程时常见的问题；下面golang学习网就来给大家整理分享一些知识点，希望能够给初学者一些帮助。本篇文章就来介绍《Python五格拼板高效解法：位运算与回溯优化》，涉及到，有需要的可以收藏一下

1. 初始实现及其性能瓶颈分析

五格拼板是一种经典的几何拼图游戏，目标是将所有12种独特的五格骨牌（Pentominoes）无缝地放入一个预设的矩形区域内。一个常见的挑战是求解5x12的矩形，已知其有1010种基本解决方案（不考虑旋转和翻转的对称性）。

最初的Python实现采用了一种基于字符数组的回溯算法来寻找解决方案。尽管能够找到一个正确解，但其性能表现不尽如人意：在5x12的板上寻找第一个解就需要约22秒，并且进行了高达23,000次的回溯调用。若要找到所有解，则可能需要数小时。

分析其主要性能瓶颈在于：

• 字符数组操作： 棋盘和拼板均以字符数组表示，每次检查有效放置或放置/移除拼板时，都需要逐个单元格进行比较和修改，效率低下。
• 实时变换计算： 拼板的旋转和翻转操作在回溯过程中动态进行，导致大量重复计算。
• 低效的启发式： find_smallest_area 函数用于寻找最小的封闭区域以进行剪枝，但其内部使用BFS（广度优先搜索）遍历，开销巨大，并且可能在搜索树中较深的位置才发挥作用。
• 重复放置检查： piece_already_placed 函数用于避免重复放置同一形状的拼板，但其实现依赖于坐标转换和排序，效率不高。

为了实现更快的求解，我们需要从根本上改变数据表示和搜索策略。

2. 优化策略与技术实现

针对上述瓶颈，以下是行之有效的优化策略：

2.1 位图表示与位运算加速

将棋盘和拼板从字符数组转换为位图（bitmask）是提升性能的关键。Python的原生大整数（int类型）可以完美地作为位图使用，通过位操作（如AND、OR、左移<<）可以极大地加速拼板的放置、移除和碰撞检测。

实现原理：

• 将棋盘视为一个一维的位序列。为了方便处理行边界，可以在每行末尾添加一个“墙”位。例如，一个宽度为width的行可以表示为width个数据位加上一个墙位。
• 拼板的形状也被转换为对应的位图。
• 通过位图的AND操作 (&) 可以快速检测拼板是否与棋盘上的已占区域重叠，或者是否超出棋盘边界。OR操作 (|) 则用于放置拼板。

# 示例：将拼板转换为位图
def piece_to_bitmap(piece, width):
    bitmap = 0
    # 棋盘每行宽度为 width + 1 (包含一个墙位)
    for line in piece:
        # int(line, 2) 将二进制字符串转换为整数
        bitmap = (bitmap << (width + 1)) | int(line, 2)
    return bitmap

# 棋盘初始化
# board = 1 << width  # 引入宽度为width的0位作为第一行
# for _ in range(height - 1):
#     board = ((board << 1) | 1) << width # 增加墙位并移位

2.2 预计算所有拼板变换及有效放置

在回溯搜索开始之前，预先计算出每种拼板的所有可能的旋转和翻转形态，并将它们转换为位图。更进一步，对于每种形态，计算出它在棋盘上所有可能的合法放置位置，并将其存储为一个位图列表。

优势：

• 避免了在搜索过程中重复进行旋转、翻转和坐标转换。
• is_valid_placement检查变为简单的位图AND操作，效率极高。

def rotate(piece):
    # 旋转拼板 (文本表示)
    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: # 0, 90, 180, 270度旋转
        transfos.append(rotate(transfos[-1]))
    transfos.extend(list(map(flip, transfos))) # 添加翻转形态
    return set(transfos) # 使用set去重

def create_piece_bitmaps(piece_text_repr, board_mask, width):
    bitmaps = []
    for rotated_piece in all_transformations(piece_text_repr):
        bitmap = piece_to_bitmap(rotated_piece, width)
        # 将此位图在整个棋盘上平移，生成所有可能的放置位置
        # 注意：这里的 board_mask 是一个包含所有“墙”位的掩码，用于判断是否越界
        # 实际实现中，更常见的是预先计算出每个piece在所有(x,y)坐标下的位图，
        # 然后在DFS中只检查与当前空位相关的那些。
        # 原始代码中的 while bitmap < board 是一个巧妙的越界检查方式
        # board 此时代表的是一个全为1的棋盘，包括墙位

        # 优化后的逻辑是：预先生成所有可能的位图，并在DFS中检查是否与当前 board 冲突
        # 这里简化为只生成所有可能的位图，不考虑与 board_mask 的重叠
        # 因为 board_mask 在这里通常指整个棋盘的边界，而不是当前已填充的区域

        # 原始代码的意图是：
        # while bitmap < board: # 确保拼板的最高位没有超出棋盘的最高位
        #     if (bitmap & board) == 0:  # 检查是否与“墙”重叠（即越界）
        #         bitmaps.append(bitmap)
        #     bitmap <<= 1 # 向右移动一位

        # 更精确的预计算方法：
        # 对于每个旋转/翻转形态，计算其在 (0,0) 位置的位图
        # 然后遍历所有 (x,y) 坐标，计算其在该坐标下的位图
        # 检查该位图是否完全在 board_mask 内部
        # 并在 DFS 中使用这些预计算的位图，与当前棋盘状态进行 & 运算判断是否冲突

        # 为了与提供的优化代码保持一致，我们使用其逻辑：
        # `board` 在 `create_piece_bitmaps` 中代表的是一个全1的，包含墙位的棋盘
        # 这样可以方便地检查拼板是否越界。

        # 假设 board_full_mask 是一个代表整个空棋盘（含墙位）的位图
        # 并且所有的 piece_bitmaps 都是相对 (0,0) 的
        # 那么在 create_piece_bitmaps 阶段，我们需要生成 piece 在所有 (x,y) 位置的位图
        # 并确保它们不超出 board_full_mask 的范围

        # 这里直接沿用优化代码的逻辑，其中 `board` 是一个全1的棋盘位图，包含墙位
        # 这意味着它是一个边界检查的掩码，而不是当前棋盘的状态
        current_board_mask = (1 << (width + 1)) - 1 # 每一行的掩码
        for _ in range(height - 1):
            current_board_mask = ((current_board_mask << 1) | 1) << width

        temp_bitmap = bitmap # 从 (0,0) 位置开始
        while temp_bitmap & current_board_mask == temp_bitmap: # 确保拼板完全在棋盘内部
            # 检查是否与“墙”重叠，这里需要更精细的边界判断
            # 原始代码的 `if (bitmap & board) == 0:` 这里的 `board` 是一个特殊构造的位图
            # 它在所有列的右侧有一个1，表示墙。如果拼板的任何位与这个墙位重叠，则无效。
            # 这里的 `board` 实际上是 `(1 << (width + 1)) - 1` 这种模式的重复
            # 也就是 `111...10111...10...`

            # 简化为：如果拼板的位图与棋盘的边界掩码相交，则有效
            # 在 create_piece_bitmaps 中，board 应该是一个表示整个可放置区域的位图
            # 并且包含“墙”位，用于判断 piece 是否越界。

            # 按照提供的优化代码，`board` 是一个预先构造好的，表示棋盘边界和行分隔符的位图
            # 例如对于 5x12， board 会是 `0...010...01...` 这种形式，
            # 其中1代表墙，0代表可放置区域。
            # 如果 `bitmap & board == 0` 意味着 piece 没有与墙重叠。

            # 这里的 `board` 变量在 `solve` 函数外部定义，但在 `create_piece_bitmaps` 内部使用
            # 这是一个闭包或全局变量的用法。
            # 假设 `board` 在这里是一个表示棋盘边界的位图。

            # 重新理解 `create_piece_bitmaps` 中的 `board` 参数
            # 它是指一个包含“墙”位的棋盘位图，用于判断 piece 是否越界
            # `if (bitmap & board) == 0:` 检查的是 piece 是否与这些“墙”位重叠
            # 如果重叠，说明 piece 跨越了行边界或超出了棋盘右边界

            # 修正此段逻辑以匹配提供的代码：
            # `board` 在 `create_piece_bitmaps` 中是指一个表示棋盘“墙”的位图
            # 其值为 `0...010...01...` (1代表墙)
            # `if (bitmap & board) == 0:` 表示拼板没有与任何墙位重叠，即没有越界。
            if (temp_bitmap & board_mask) == 0: # board_mask是棋盘的墙位掩码
                bitmaps.append(temp_bitmap)
            temp_bitmap <<= 1 # 尝试下一个位置
    return bitmaps

2.3 改进的启发式：最少可能性（Minimum Remaining Values）

原始代码中的find_smallest_area是一个昂贵的剪枝策略。更有效的策略是“最少可能性”启发式（Minimum Remaining Values，MRV），也称为“最受约束变量优先”：

• 在每次回溯时，不寻找下一个空闲单元格，而是寻找棋盘上最难被拼板覆盖的空闲单元格。
• 具体来说，选择一个空闲单元格，计算有多少种剩余的拼板（及其所有变换）能够覆盖它。
• 选择那个能被最少种类拼板覆盖的单元格作为下一个放置点。
• 如果某个单元格无法被任何剩余拼板覆盖，则说明当前路径无解，立即回溯。

优势：

• 这能更快地发现死胡同，从而大大剪枝搜索树。
• 不再需要昂贵的BFS来寻找最小区域，因为“无法覆盖”的检测将自动完成剪枝。

def get_candidates(current_board_state, piece_bitmaps_precomputed, width, height):
    # current_board_state 是当前已填充的棋盘位图
    # piece_bitmaps_precomputed 是预计算好的 {piece_name: [bitmap1, bitmap2, ...]}

    least_fillers = []
    least = float('inf')

    # rowmask 用于定位每一行，并跳过墙位
    # 初始 rowmask 覆盖第一行 (width个数据位 + 1个墙位)
    rowmask = (1 << (width + 1)) - 1 

    for _ in range(height):
        # 找到当前行中未被占用的位 (1表示空闲)
        # current_board_state & rowmask 得到当前行的状态
        # (current_board_state & rowmask) ^ rowmask 翻转位，得到空闲位
        bitrow = (current_board_state & rowmask) ^ rowmask
        rowmask <<= (width + 1) # 移动到下一行

        if not bitrow: # 如果此行完全被占用
            continue

        # 找到当前行中最左边的空闲单元格 (最低位的1)
        # bitrow & -bitrow 是一个技巧，可以得到最低位的1
        cell = bitrow & -bitrow 

        fillers = []
        # 遍历所有剩余的拼板，看它们是否能覆盖这个 cell
        for key, bitmaps in piece_bitmaps_precomputed.items():
            for bitmap in bitmaps:
                # 1. cell & bitmap：检查这个拼板的位图是否包含我们选定的空闲单元格
                # 2. bitmap & current_board_state == 0：检查这个拼板是否与棋盘上已放置的拼板冲突
                if (cell & bitmap) and (bitmap & current_board_state == 0):
                    fillers.append((key, bitmap))
                    if len(fillers) >= least: # 如果当前单元格的填充可能性已不优于已知最小值
                        break # 提前退出内层循环，无需再检查该拼板的其他形态
            else: # 如果内层循环没有被break (即该key的所有形态都检查完了，且没有达到least)
                continue # 继续检查下一个key
            break # 如果内层循环被break (即达到了least)，则外层循环也应该break，因为已经没有改进空间
        else: # 如果外层循环没有被break (即所有key都检查完了，或者找到了更好的least)
            # 如果当前单元格的填充可能性少于之前找到的最小值，则更新
            if len(fillers) < least:
                least = len(fillers)
                least_fillers = fillers

    return least_fillers # 返回最少可能性单元格对应的所有可放置拼板及其位图

2.4 延迟字符串表示

将解决方案从位图转换为可打印的字符网格，应该只在找到一个完整解时才进行。在回溯过程中，所有操作都应基于位图，避免不必要的字符串转换和拼接开销。

3. 优化后的Python实现

将上述策略整合到代码中，可以得到一个高效的五格拼板求解器。

import datetime

def solve(height, width, pieces_text_repr):
    # 辅助函数：旋转拼板的文本表示
    def rotate(piece):
        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:
            transfos.append(rotate(transfos[-1]))
        # 使用 set 去重，因为某些拼板在翻转后可能与旋转后的形态相同
        # 例如 'X' 拼板
        return set(transfos + list(map(flip, transfos)))

    # 辅助函数：将拼板的文本表示转换为位图
    def piece_to_bitmap(piece):
        bitmap = 0
        for line in piece:
            # 每行宽度为 width + 1，其中 +1 是为了添加“墙”位
            bitmap = (bitmap << (width + 1)) | int(line, 2)
        return bitmap

    # 预处理：为每个拼板生成所有可能的位图放置位置
    def create_piece_bitmaps(piece_text_repr):
        bitmaps = []
        for rotated_piece in all_transformations(piece_text_repr):
            bitmap = piece_to_bitmap(rotated_piece)
            # 将此位图在整个棋盘上平移，生成所有可能的放置位置
            # 这里的 `board_wall_mask` 是一个表示棋盘“墙”的位图
            # 如果 `bitmap & board_wall_mask == 0`，表示拼板没有与墙重叠，即合法
            temp_bitmap = bitmap
            # 循环直到拼板的最高位超出棋盘的最高位，或者拼板与墙重叠
            # 这里的 board_limit 是一个表示棋盘总大小的上限，用于循环条件
            while temp_bitmap < board_limit: 
                # 检查拼板是否与棋盘的“墙”位重叠（即是否越界）
                if (temp_bitmap & board_wall_mask) == 0:  
                    bitmaps.append(temp_bitmap)
                temp_bitmap <<= 1 # 向右移动一位，尝试下一个位置
        return bitmaps

    # 启发式函数：获取最少可能性单元格的所有可放置拼板
    def get_candidates(current_board_state, piece_bitmaps_precomputed):
        least_fillers = []
        least = float('inf')

        # rowmask 用于迭代每一行，定位行内的空闲单元格
        rowmask = (1 << (width + 1)) - 1 

        for _ in range(height):
            # 获取当前行中未被占用的位 (1表示空闲，0表示已占用或墙)
            bitrow = (current_board_state & rowmask) ^ rowmask
            rowmask <<= (width + 1) # 移动到下一行

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

            # 找到当前行中最左边的空闲单元格 (最低位的1)
            cell_to_cover = bitrow & -bitrow 

            fillers = []
            # 遍历所有剩余的拼板类型
            for key, bitmaps in piece_bitmaps_precomputed.items():
                for bitmap in bitmaps:
                    # 检查：
                    # 1. 拼板的位图是否覆盖了目标空闲单元格 (cell_to_cover & bitmap)
                    # 2. 拼板是否与棋盘上已放置的区域冲突 (bitmap & current_board_state == 0)
                    if (cell_to_cover & bitmap) and (bitmap & current_board_state == 0):
                        fillers.append((key, bitmap))
                        if len(fillers) >= least: # 如果当前单元格的填充可能性已不优于已知最小值，提前退出
                            break
                else: # 如果内层循环没有被break (即该key的所有形态都检查完了，且没有达到least)
                    continue 
                break # 如果内层循环被break (即达到了least)，则外层循环也应该break
            else: # 如果外层循环没有被break (即所有key都检查完了，或者找到了更好的least)
                # 如果当前单元格的填充可能性少于之前找到的最小值，则更新
                if len(fillers) < least:
                    least = len(fillers)
                    least_fillers = fillers

        return least_fillers # 返回最少可能性单元格对应的所有可放置拼板及其位图

    # 核心回溯函数 (DFS)
    def dfs(current_board_state, piece_bitmaps_remaining, current_moves):
        # 

以上就是《Python五格拼板优化解法：位运算与回溯技巧》的详细内容，更多关于的资料请关注golang学习网公众号！