pentomino 拼图是一种经典的几何谜题，由十二种形状各异、由五个正方形组成的拼块构成。解决这类拼图通常需要将所有拼块无缝地放入一个预设的矩形区域内。最初的 python 实现虽然能够找到一个解决方案，但在处理 5x12 这种具有大量解（维基百科指出有 1010 种基本解）的棋盘时，其效率低下，单个解需要数十秒，导致寻找所有解可能耗时数小时。这主要源于低效的数据结构、重复的计算以及缺乏有效的搜索剪枝策略。为了大幅提升求解效率，我们将介绍一系列优化技术，包括采用位图表示、预计算拼块形态和引入启发式搜索。
要将 Pentomino 求解器的性能从数小时提升到数分钟，需要从根本上改变数据表示和搜索策略。
传统的棋盘表示通常是二维字符数组或列表，每次检查拼块放置的有效性或进行移除操作时，都需要遍历多个单元格并进行字符比较。这种方法效率较低。
优化方案： 采用位图（Bitmap）来表示棋盘和拼块。
原始实现在回溯搜索过程中，会动态地对拼块进行旋转和翻转，并检查其有效性。这种重复计算会显著增加搜索时间。
立即学习“Python免费学习笔记（深入）”；
优化方案： 在搜索开始前，对每个拼块预先计算其所有可能的旋转和翻转形态，并将这些形态转换为位图，存储在一个列表中。
回溯算法的效率很大程度上取决于如何选择下一个待填充的空位。原始实现简单地寻找下一个空位，这可能导致进入不必要的递归分支。
优化方案： 采用“最小选择原则”（或称“最受限变量”启发式，即“fail-first principle”）来选择下一个放置拼块的位置。
在搜索过程中，将位图形式的解决方案转换为可读的字符网格是耗时的操作。
优化方案： 仅当找到一个完整解决方案时，才将其位图表示转换为可打印的字符串格式。
以下是应用上述优化原则后的 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)
代码解析要点：
经过上述优化后，求解器的性能得到了显著提升：
关于解决方案数量： 维基百科指出 5x12 棋盘有 1010 种基本解决方案。本实现找到 4040 个解决方案，这是因为本程序将旋转和镜像对称的解决方案也视为不同的解。例如，如果一个解 A 经过整体翻转或旋转后得到解 B，那么 A 和 B
以上就是Python 俄罗斯方块拼图求解器优化：位图与启发式搜索提速的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
879
收藏
