连五格拼图是一种经典的平面几何拼图游戏，目标是将12个形状各异、由5个正方形组成的拼块（pentominoes）无缝填充到指定大小的矩形区域内。在python中实现一个求解器，初版通常采用回溯算法。然而，对于5x12这样的标准棋盘，原始实现面临着严重的性能瓶颈。例如，一个未经优化的python求解器可能需要22秒才能找到一个解，并且会产生高达23,000次不必要的递归调用。考虑到5x12棋盘理论上存在1010种解决方案（不计镜像），若要找到所有解，原始算法可能需要数小时甚至更长时间，这显然是不可接受的。
性能低下的主要原因在于：
为了大幅提升求解效率，我们引入了以下关键优化策略：
将棋盘和拼块表示为位图是提升性能最核心的改变。Python的原生大整数支持位操作，这使得位图操作异常高效。
# 示例：将拼块转换为位图
def piece_to_bitmap(piece, width):
bitmap = 0
# 假设piece是元组列表，例如 ("011", "110", "010")
# 每一行转换为二进制整数，然后左移 (width + 1) 位
# 这里的width是棋盘宽度，+1是为了预留墙位
for line in piece:
bitmap = (bitmap << (width + 1)) | int(line, 2)
return bitmap
# 棋盘位图初始化
# board = 1 << width # 引入宽度为0的行
# for _ in range(height - 1):
# board = ((board << 1) | 1) << width # 每行末尾加1作为墙，然后左移宽度位为了避免在搜索过程中重复计算拼块的旋转和翻转，所有可能的变换形式及其在棋盘上的有效放置位置都在预处理阶段生成并存储。
立即学习“Python免费学习笔记（深入）”；
def rotate(piece):
# 实现拼块的90度旋转
# ...
pass
def flip(piece):
# 实现拼块的水平翻转
# ...
pass
def all_transformations(piece):
# 生成所有独特的旋转和翻转形式
transfos = [piece]
while len(transfos) < 4:
transfos.append(rotate(transfos[-1]))
transfos.extend(list(map(flip, transfos)))
return set(transfos) # 使用set去重
def create_piece_bitmaps(piece, board_mask, width):
bitmaps = []
for rotated_piece in all_transformations(piece):
bitmap = piece_to_bitmap(rotated_piece, width)
# 将拼块位图在整个棋盘上移动，检查是否与棋盘边界或墙重叠
# board_mask用于检查边界，这里假设board_mask已经包含了墙位
while bitmap < board_mask: # 确保拼块在棋盘范围内
if (bitmap & board_mask) == 0: # 检查是否与墙重叠 (0表示不重叠)
bitmaps.append(bitmap)
bitmap <<= 1 # 右移一位
return bitmaps传统的深度优先搜索（DFS）可能随意选择下一个空位进行填充。然而，更有效的策略是采用“最受限变量”（Most Constrained Variable, MCV）启发式，也称为“最小剩余值”（Minimum Remaining Values, MRV）启发式。
def get_candidates(board_state, piece_bitmaps, height, width):
least_fillers = []
least = float('inf')
rowmask = (1 << (width + 1)) - 1 # 用于提取单行
for _ in range(height):
# 找到当前行第一个空闲单元格
# bitrow表示当前行中空闲的单元格（1表示空闲）
bitrow = (board_state & rowmask) ^ rowmask
rowmask <<= (width + 1) # 移动到下一行
if not bitrow: # 如果本行已满
continue
cell = bitrow & -bitrow # 获取第一个1位（即第一个空闲单元格）
# 检查哪些拼块可以覆盖这个单元格
fillers = []
for key, bitmaps in piece_bitmaps.items():
for bitmap in bitmaps:
# 如果拼块位图覆盖了当前空闲单元格，且与当前棋盘状态不冲突
if (cell & bitmap) and (bitmap & board_state) == 0:
fillers.append((key, bitmap))
if len(fillers) >= least: # 如果当前拼块数量已经不比之前的“最少”好，则提前跳出
break
else: # 如果内层循环没有break，说明当前key的所有bitmaps都尝试完了
continue # 继续外层循环
break # 如果内层循环break了，说明找到了一个不比least好的情况，直接跳出当前key的循环
# 更新最少填充者
if len(fillers) < least:
least = len(fillers)
least_fillers = fillers
return least_fillers仅在找到一个完整解决方案时，才将位图表示的棋盘转换为可读的字符表示。这避免了在回溯过程中频繁进行昂贵的字符串转换操作。
import datetime
def solve(height, width, pieces_input):
# --- 辅助函数：拼块变换 ---
def rotate(piece_grid):
# 将拼块网格逆时针旋转90度
# piece_grid: tuple of strings, e.g., ("011", "110", "010")
lst = [""] * len(piece_grid[0])
for line in piece_grid:
for j, ch in enumerate(line):
lst[j] += ch
return tuple(reversed(lst)) # 逆时针旋转
def flip(piece_grid):
# 水平翻转拼块网格
return tuple(reversed(piece_grid)) # 反转行序
def all_transformations(piece_grid):
# 生成一个拼块的所有独特变换形式（旋转和翻转）
transfos = [piece_grid]
current_piece = piece_grid
for _ in range(3): # 旋转3次（共4个方向）
current_piece = rotate(current_piece)
if current_piece not in transfos: # 避免重复
transfos.append(current_piece)
# 对所有旋转后的形式进行翻转
flipped_transfos = []
for p in transfos:
flipped_p = flip(p)
if flipped_p not in transfos and flipped_p not in flipped_transfos:
flipped_transfos.append(flipped_p)
transfos.extend(flipped_transfos)
return set(transfos) # 使用set去重
# --- 辅助函数：位图转换 ---
def piece_to_bitmap(piece_grid):
# 将拼块网格转换为位图
bitmap = 0
for line in piece_grid:
# 每行后加一个“墙”位 (width + 1)
bitmap = (bitmap << (width + 1)) | int(line, 2)
return bitmap
def create_piece_bitmaps(piece_key, piece_grid):
# 为给定拼块生成所有可能的有效放置位图
bitmaps = []
for transformed_piece in all_transformations(piece_grid):
bitmap = piece_to_bitmap(transformed_piece)
# 将此位图在整个棋盘上移动，检查是否与“墙”或边界重叠
# board_mask用于定义棋盘边界和墙
current_bitmap = bitmap
# 循环直到拼块位图超出棋盘范围
while current_bitmap < board_mask:
# 检查拼块是否与棋盘的“墙”重叠 (0表示不重叠)
if (current_bitmap & board_mask) == 0:
bitmaps.append(current_bitmap)
current_bitmap <<= 1 # 向右移动一位
return bitmaps
# --- 启发式搜索：选择最受限的空位 ---
def get_candidates(current_board, remaining_piece_bitmaps):
# 寻找棋盘上第一个空闲单元格，并计算有多少种拼块可以覆盖它
# 优先选择那些能被最少拼块覆盖的单元格
least_fillers = []
least = float('inf')
# rowmask用于从整个棋盘位图中提取单行
rowmask = (1 << (width + 1)) - 1
for _ in range(height):
# bitrow表示当前行中空闲的单元格（1表示空闲）
bitrow = (current_board & rowmask) ^ rowmask
rowmask <<= (width + 1) # 移动到下一行
if not bitrow: # 如果本行已满
continue
# 获取第一个1位（即第一个空闲单元格）
cell = bitrow & -bitrow
# 检查哪些剩余的拼块可以覆盖这个空闲单元格
fillers = []
for key, bitmaps in remaining_piece_bitmaps.items():
for bitmap in bitmaps:
# 如果拼块位图覆盖了当前空闲单元格，且与当前棋盘状态不冲突
if (cell & bitmap) and (bitmap & current_board) == 0:
fillers.append((key, bitmap))
if len(fillers) >= least: # 如果当前拼块数量已经不比之前的“最少”好，则提前跳出
break
else: # 如果内层循环没有break，说明当前key的所有bitmaps都尝试完了
continue # 继续外层循环
break # 如果内层循环break了，说明找到了一个不比least好的情况，直接跳出当前key的循环
# 更新最少填充者
if len(fillers) < least:
least = len(fillers)
least_fillers = fillers
return least_fillers
# --- 核心搜索算法：深度优先搜索 (DFS) ---
def dfs(current_board, remaining_piece_bitmaps, current_moves):
if not remaining_piece_bitmaps: # 所有拼块都已放置
yield current_moves # 返回一个解
return
# 获取下一个要填充的空位及其可能的填充拼块
candidates = get_candidates(current_board, remaining_piece_bitmaps)
if not candidates: # 如果没有有效的候选拼块可以填充，说明当前路径无解
return
for key, move_bitmap in candidates:
# 从剩余拼块中移除当前选中的拼块
# 创建新的字典，不包含已放置的拼块
next_remaining_pieces = {k: v for k, v in remaining_piece_bitmaps.items() if k != key}
# 递归调用DFS
yield from dfs(
current_board | move_bitmap, # 更新棋盘状态（放置拼块）
next_remaining_pieces,
{**current_moves, key: move_bitmap} # 记录当前移动
)
# --- 解决方案打印 ---
def print_solution(solution_map):
# 将位图解决方案转换为可读的字符网格
cell_mask = 1
output_str = []
for _ in range(height):
row_str = []
for _ in range(width):
# 找到覆盖当前单元格的拼块名称
key = next(key for key, bitmap in solution_map.items()
if cell_mask & bitmap)
row_str.append(key)
cell_mask <<= 1 # 移动到下一个单元格
output_str.append("".join(row_str))
cell_mask <<= 1 # 跳过“墙”位
print("\n".join(output_str))
print()
# --- 初始化 ---
start_time = datetime.datetime.now()
# 构建棋盘的位图掩码，包含“墙”位
board_mask = 1 << width # 第一行末尾的墙
for _ in range(height - 1):
board_mask = ((board_mask << 1) | 1) << width # 后续行末尾的墙
# 预处理所有拼块的所有变换形式及其有效放置位图
piece_bitmaps = {}
for key, piece_grid in pieces_input.items():
piece_bitmaps[key] = create_piece_bitmaps(key, piece_grid)
# 开始深度优先搜索
solution_count = 0
for solution in dfs(board_mask, piece_bitmaps, {}):
solution_count += 1
print(solution_count, ":")
print_solution(solution)
end_time = datetime.datetime.now()
print(f"总共找到 {solution_count} 个解决方案。")
print(f"总耗时: {(end_time - start_time).total_seconds():.2f} 秒")
# --- 示例调用 ---
# 拼块定义采用更直观的网格字符串形式
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的连五格拼图问题时，性能得到了显著提升。
尽管Python通过位操作和启发式搜索取得了巨大进步，但对于追求极致性能的应用场景，仍然存在进一步优化的空间：
本教程详细展示了如何通过一系列精心设计的优化策略，将一个原本低效的Python连五格拼图求解器转化为一个高性能的解决方案。核心思想包括：使用位图进行高效数据表示、预处理减少运行时计算、以及运用启发式搜索（最受限变量）来有效剪枝。这些技术不仅适用于连五格拼图，也为其他组合优化和回溯问题提供了通用的优化思路，强调了数据结构选择和算法策略在性能优化中的决定性作用。
以上就是Python 连五格拼图求解器优化：位图与启发式搜索策略应用的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
989
收藏
