Python高效求解五格拼板：位运算与回溯优化实践-Python教程-PHP中文网

Python高效求解五格拼板：位运算与回溯优化实践

本文旨在探讨如何优化Python中的五格拼板（Pentomino）求解器，将其从耗时数小时的低效实现提升至数分钟内完成所有解的专业级性能。通过引入位图表示、预计算所有拼板变换、采用“最少可能性”启发式剪枝以及延迟字符串渲染等关键技术，显著减少了回溯搜索的深度和广度，从而实现高效求解。

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

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

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

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

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

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

2. 优化策略与技术实现

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

立即学习“Python免费学习笔记（深入）”；

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高效求解五格拼板：位运算与回溯优化实践的详细内容，更多请关注php中文网其它相关文章！