本文探讨了如何优化 Pentomino 拼图求解器，旨在从耗时数小时寻找单个解提升至数分钟内找到所有解。核心策略包括：采用位图高效表示棋盘和拼块，利用位运算加速操作；预先计算所有拼块的旋转和翻转形态，避免运行时重复计算；引入“最小选择”启发式搜索，优先处理最难放置的区域，从而显著剪枝搜索树，提高回溯效率；并推迟最终解的字符串格式化，以专注于核心计算。
引言
pentomino 拼图是一种经典的几何谜题，由十二种形状各异、由五个正方形组成的拼块构成。解决这类拼图通常需要将所有拼块无缝地放入一个预设的矩形区域内。最初的 python 实现虽然能够找到一个解决方案，但在处理 5×12 这种具有大量解（维基百科指出有 1010 种基本解）的棋盘时，其效率低下，单个解需要数十秒，导致寻找所有解可能耗时数小时。这主要源于低效的数据结构、重复的计算以及缺乏有效的搜索剪枝策略。为了大幅提升求解效率，我们将介绍一系列优化技术，包括采用位图表示、预计算拼块形态和引入启发式搜索。
核心优化原则
要将 Pentomino 求解器的性能从数小时提升到数分钟，需要从根本上改变数据表示和搜索策略。
1. 位图表示与位运算
传统的棋盘表示通常是二维字符数组或列表，每次检查拼块放置的有效性或进行移除操作时，都需要遍历多个单元格并进行字符比较。这种方法效率较低。
优化方案： 采用位图（Bitmap）来表示棋盘和拼块。
- 棋盘表示： 将整个棋盘视为一个大的整数。每个位代表棋盘上的一个单元格。通过在每行末尾添加一个额外的位（作为“墙”），可以简化行边界检查和位移操作。例如，一个 width 宽度的行加上一个墙位，总共占用 width + 1 位。
- 拼块表示： 同样，每个拼块的不同形态和位置也可以表示为一个位图。
- 优势： Python 的原生大整数支持位运算（如 &、|、
2. 预计算所有拼块变换
原始实现在回溯搜索过程中，会动态地对拼块进行旋转和翻转，并检查其有效性。这种重复计算会显著增加搜索时间。
立即学习“Python免费学习笔记（深入）”；
优化方案： 在搜索开始前，对每个拼块预先计算其所有可能的旋转和翻转形态，并将这些形态转换为位图，存储在一个列表中。
- 过程： 对于每个拼块，生成其 0°、90°、180°、270° 旋转后的形态，然后对这些形态分别进行水平翻转，得到所有独特的变换。
- 存储： 将这些变换后的拼块位图以及它们在棋盘上所有合法的位置（不超出边界且不与“墙”重叠）一并预计算并存储。
- 优势： 搜索时，只需从预计算好的列表中选择拼块的特定位图，无需在运行时进行复杂的几何变换和有效性检查，极大地减少了计算开销。
3. 启发式搜索：最小选择原则 (Most Constrained Variable)
回溯算法的效率很大程度上取决于如何选择下一个待填充的空位。原始实现简单地寻找下一个空位，这可能导致进入不必要的递归分支。
优化方案： 采用“最小选择原则”（或称“最受限变量”启发式，即“fail-first principle”）来选择下一个放置拼块的位置。
- 策略： 不再简单地寻找第一个空闲单元格，而是寻找棋盘上“最难覆盖”的空闲单元格——即能够放置的拼块数量最少的那个单元格。
- 实现： 遍历棋盘（可以简化为每行的第一个空闲单元格），对于每个空闲单元格，统计有多少个拼块（及其所有变换）能够覆盖它。选择那个能被最少拼块覆盖的单元格。
- 优势： 这种策略能够更快地发现无解的分支，从而提前进行回溯，显著剪枝搜索树的宽度，避免大量无效的递归调用。例如，如果某个单元格无法被任何剩余拼块覆盖，则立即回溯。这同时也替代了昂贵的“寻找最小封闭区域”的检查。
4. 延迟结果格式化
在搜索过程中，将位图形式的解决方案转换为可读的字符网格是耗时的操作。
优化方案： 仅当找到一个完整解决方案时，才将其位图表示转换为可打印的字符串格式。
- 优势： 将格式化操作从搜索循环中移出，确保搜索过程专注于核心的位图计算和逻辑判断，进一步提升搜索效率。
实现细节与代码解析
以下是应用上述优化原则后的 Python 求解器代码：
import datetime def solve(height, width, pieces): # 辅助函数：旋转拼块 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: # 旋转3次得到所有90度旋转 transfos.append(rotate(transfos[-1])) # 添加翻转形态 transfos.extend(list(map(flip, transfos))) # 使用set去重并转换回tuple return set(transfos) # 辅助函数：将拼块（字符串元组表示）转换为位图 def piece_to_bitmap(piece): bitmap = 0 for line in piece: # 每行通过 (width + 1) 位移，为“墙”预留一位 bitmap = (bitmap << (width + 1)) | int(line, 2) return bitmap # 辅助函数：为每个拼块创建所有可能的位图形式及其在棋盘上的所有合法位置 def create_piece_bitmaps(piece): bitmaps = [] for rotated_piece in all_transformations(piece): bitmap = piece_to_bitmap(rotated_piece) # 将此位图在整个棋盘上移动，生成所有合法位置的位图 # 这里的 board 变量是全局的，代表了棋盘的边界和“墙” temp_bitmap = bitmap while temp_bitmap < board_boundary_mask: # 确保不超出棋盘总范围 # 检查是否与“墙”重叠 (bitmap & board) == 0 表示不重叠 # 这里的 board 变量在调用前被初始化为只包含“墙”的掩码 if (temp_bitmap & board_wall_mask) == 0: bitmaps.append(temp_bitmap) temp_bitmap <<= 1 # 向右移动一位 return bitmaps # 启发式函数：找到最受限的空闲单元格，并返回可覆盖它的拼块列表 def get_candidates(current_board_state, piece_bitmaps): least_fillers = [] least = float('inf') # rowmask 用于定位每行 rowmask = (1 << (width + 1)) - 1 # 包含width个单元格和1个墙位 for _ in range(height): # 找到当前行中空闲的单元格 (1-bit 表示空闲) # current_board_state & rowmask 获取当前行的占用情况 # (current_board_state & rowmask) ^ rowmask 翻转位，1表示空闲 bitrow = (current_board_state & rowmask) ^ rowmask rowmask <<= width + 1 # 移动到下一行 if not bitrow: # 如果此行完全被占用，则跳过 continue # 找到当前行第一个空闲单元格（最低位的1） cell = bitrow & -bitrow fillers = [] # 检查哪些拼块可以覆盖这个单元格 for key, bitmaps in piece_bitmaps.items(): for bitmap in bitmaps: # 如果拼块位图覆盖了当前空闲单元格，且不与当前棋盘状态重叠 if (cell & bitmap) and (bitmap & current_board_state) == 0: fillers.append((key, bitmap)) if len(fillers) >= least: # 如果已找到的填充物数量不比当前最小的少，则无需继续检查此拼块 break else: # 如果内层循环没有break，说明当前拼块的所有变换都检查完了 continue # 继续外层循环检查下一个拼块 break # 如果内层循环break了，说明当前拼块已找到足够多的填充物，无需继续检查此拼块 else: # 如果外层循环没有break，说明当前行所有拼块都检查完了 # 发现更小的填充物数量，更新最小选择 if len(fillers) < least: least = len(fillers) least_fillers = fillers return least_fillers # 深度优先搜索（回溯）函数，使用生成器 yielding 所有解决方案 def dfs(current_board_state, remaining_piece_bitmaps, current_moves): # 如果所有拼块都已放置，则找到一个解决方案 if not remaining_piece_bitmaps: yield current_moves return # 获取当前最受限的单元格及其可放置的拼块列表 candidates = get_candidates(current_board_state, remaining_piece_bitmaps) if not candidates: # 如果没有候选拼块可以放置，则此路径无解 return for key, move_bitmap in candidates: # 尝试放置拼块 # 创建新的棋盘状态 new_board_state = current_board_state | move_bitmap # 从剩余拼块中移除当前拼块 new_remaining_piece_bitmaps = {k: v for k, v in remaining_piece_bitmaps.items() if k != key} # 递归调用 DFS yield from dfs( new_board_state, new_remaining_piece_bitmaps, {**current_moves, key: move_bitmap} # 更新当前已放置的拼块 ) # 辅助函数：打印解决方案 def print_solution(solution): cell_mask = 1 # 用于定位每个单元格的位掩码 output_grid = [[' ' for _ in range(width)] for _ in range(height)] # 遍历棋盘的每个单元格 for r in range(height): for c in range(width): # 找到覆盖当前单元格的拼块 for key, bitmap in solution.items(): if (cell_mask & bitmap) != 0: # 如果当前单元格位在拼块位图中为1 output_grid[r][c] = key break cell_mask <<= 1 # 移动到下一个单元格 cell_mask <<= 1 # 跳过“墙”位，移动到下一行的第一个单元格 for row in output_grid: print("".join(row)) print() # 初始化棋盘位图掩码 # board_wall_mask 用于检查拼块是否与“墙”重叠 board_wall_mask = 0 # board_boundary_mask 用于检查拼块是否超出棋盘总范围 board_boundary_mask = 0 # 构造棋盘的“墙”和边界掩码 # 每一行包含 width 个单元格和一个“墙”位 (width + 1) for r in range(height): # 每一行的“墙”位是该行最左侧的位（最高位） board_wall_mask |= (1 << (r * (width + 1) + width)) # 每一行的所有单元格位 board_boundary_mask |= (((1 << width) - 1) << (r * (width + 1))) # 生成所有拼块的所有可能位置的位图 # piece_bitmaps 字典存储 {拼块名称: [所有合法位置的位图]} all_precomputed_piece_bitmaps = { key: create_piece_bitmaps(piece) for key, piece in pieces.items() } print("开始搜索解决方案...") start_time = datetime.datetime.now() solution_count = 0 # 调用 DFS 搜索所有解决方案 for solution in dfs(0, all_precomputed_piece_bitmaps, {}): # 初始棋盘状态为0（空） solution_count += 1 print(f"{solution_count} :") print_solution(solution) end_time = datetime.datetime.now() print(f"总共找到 {solution_count} 个解决方案。") print(f"总耗时: {(end_time - start_time).total_seconds():.2f} 秒") # 示例调用 # 拼块定义使用字符串元组，1表示拼块部分，0表示空 # 这样更直观，且方便转换为二进制 pentomino_pieces = { 'F': ("011", "110", "010"), 'W': ("100", "110", "011"), 'V': ("100", "100", "111"), 'X': ("010", "111", "010"), 'N': ("1100", "0111"), 'P': ("111", "011"), 'U': ("111", "101"), 'Z': ("100", "111", "001"), 'I': ("11111", ), 'Y': ("1111", "0100"), 'T': ("111", "010", "010"), 'L': ("1111", "1000") } solve(5, 12, pentomino_pieces)
代码解析要点：
- rotate 和 flip： 实现了拼块的旋转和翻转逻辑，输入是字符串元组形式的拼块。
- all_transformations： 调用 rotate 和 flip，生成一个拼块的所有 8 种（或更少，取决于对称性）独特的几何变换。使用 set 去重确保只存储唯一的形态。
- piece_to_bitmap： 将字符串元组表示的拼块转换为整数位图。关键在于 (bitmap
- create_piece_bitmaps： 这是预计算阶段的核心。它遍历一个拼块的所有几何变换，然后将每个变换在棋盘上进行平移，生成该拼块所有可能的合法放置位置的位图。board_wall_mask 用于检查拼块是否跨越了行边界（即与“墙”重叠）。
- get_candidates： 实现了“最小选择原则”启发式。它遍历棋盘的空闲单元格（这里为了效率，只检查每行的第一个空闲单元格），计算有多少个剩余拼块可以覆盖它，并返回能够覆盖最少拼块的那个单元格及其对应的拼块列表。
- dfs： 深度优先搜索的回溯函数。它接收当前的棋盘状态、剩余的拼块位图以及已放置的拼块信息。yield 关键字使得函数成为一个生成器，能够逐个返回所有找到的解决方案，而不是在找到第一个解后就停止。
- print_solution： 将位图形式的解决方案转换为易于阅读的字符网格。
性能提升与结果分析
经过上述优化后，求解器的性能得到了显著提升：
- 原始实现： 在一台普通 PC 上，寻找一个 5×12 棋盘的解决方案大约需要 22 秒，并且伴随 23k 次的回溯调用。
- 优化后： 在相同或类似的硬件上，优化后的 Python 代码能够在约 5 分钟内找到所有 4040 个解决方案。与原始实现相比，这是一个巨大的进步，将时间从数小时缩短到数分钟，并且找到了所有解而非单个解。
关于解决方案数量： 维基百科指出 5×12 棋盘有 1010 种基本解决方案。本实现找到 4040 个解决方案，这是因为本程序将旋转和镜像对称的解决方案也视为不同的解。例如，如果一个解 A 经过整体翻转或旋转后得到解 B，那么 A 和 B
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
