Python Pentomino求解器性能优化：如何快速获取全部棋盘解？

我小时候常玩Ubongo桌游，最近接触到Pentomino谜题，于是用Python实现了一款自定义求解器。以下是我的代码：

import datetime

def solve(height, width, pieces):
    sorted_pieces = sort_pieces_by_length(pieces)
    board = [['' for _ in range(width)] for _ in range(height)]
    result = []
    counter = 0

    def is_valid_placement(piece, x, y):
        first_coord = piece[0]
        if not (0 <= x < width and 0 <= y < height) or board[y][x] != '':
            return False
        for px, py in piece[1:]:
            nx, ny = x + px - first_coord[0], y + py - first_coord[1]
            if not (0 <= nx < width and 0 <= ny < height) or board[ny][nx] != '':
                return False
        return True

    def place_piece(piece, x, y, char):
        first_coord = piece[0]
        board[y][x] = char
        for px, py in piece[1:]:
            nx, ny = x + px - first_coord[0], y + py - first_coord[1]
            board[ny][nx] = char

    def remove_piece(piece, x, y):
        first_coord = piece[0]
        board[y][x] = ''
        for px, py in piece[1:]:
            nx, ny = x + px - first_coord[0], y + py - first_coord[1]
            board[ny][nx] = ''

    def find_smallest_area():

        visited = set()
        smallest_area = height * width
        occupied_tiles = 0

        for y in range(height):
            for x in range(width):
                if board[y][x] != '':
                    occupied_tiles += 1

        def bfs(start_x, start_y):
            nonlocal smallest_area
            queue = [(start_x, start_y)]
            area = 0

            while queue:
                curr_x, curr_y = queue.pop(0)
                if (curr_x, curr_y) in visited or not (0 <= curr_x < width and 0 <= curr_y < height) or board[curr_y][curr_x] != '':
                    continue

                visited.add((curr_x, curr_y))
                area += 1

                for dir_x, dir_y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    new_x, new_y = curr_x + dir_x, curr_y + dir_y
                    queue.append((new_x, new_y))

            smallest_area = min(smallest_area, area)

        for y in range(height):
            for x in range(width):
                if occupied_tiles + len(visited) == height * width:
                    return smallest_area
                if (x, y) not in visited and board[y][x] == '':
                    bfs(x, y)

        return smallest_area

    def rotateR(piece_coords):
        return sorted([[y, -x] for x, y in piece_coords], key=lambda coord: (coord[0], coord[1]))

    def rotateH(piece_coords):
        return sorted([[-x, y] for x, y in piece_coords], key=lambda coord: (coord[0], coord[1]))

    def backtrack(piece_index):
        nonlocal result,counter
        counter+=1
        if piece_index == len(sorted_pieces):
            result.append([row[:] for row in board])
            return True

        piece_name, piece_coords = list(sorted_pieces.items())[piece_index]
        reset_coords = piece_coords

        def try_place(x, y, piece_coords, placed_pieces, piece_index):
            if not piece_already_placed(piece_coords, placed_pieces):
                place_piece(piece_coords, x, y, piece_name)
                placed_pieces.append(piece_coords)
                if find_smallest_area() >= 5 and backtrack(piece_index + 1):
                    return True

                remove_piece(piece_coords, x, y)
                return False

        for y in range(height):
            for x in range(width):
                if board[y][x] != '':
                    continue
                placed_pieces = []
                piece_coords = reset_coords

                if is_valid_placement(piece_coords, x, y):
                    if try_place(x, y, piece_coords, placed_pieces, piece_index):
                        return True

                for _ in range (3):
                    piece_coords = rotateR(piece_coords)

                    if is_valid_placement(piece_coords, x, y):
                        if try_place(x, y, piece_coords, placed_pieces, piece_index):
                            return True
                piece_coords = reset_coords
                piece_coords = rotateH(piece_coords)

                if is_valid_placement(piece_coords, x, y):
                    if try_place(x, y, piece_coords, placed_pieces, piece_index):
                        return True

                for _ in range (3):
                    piece_coords = rotateR(piece_coords)

                    if is_valid_placement(piece_coords, x, y):
                        if try_place(x, y, piece_coords, placed_pieces, piece_index):
                            return True



        return False
    start_time = datetime.datetime.now()
    backtrack(0)
    print("TOTAL BACKTRACKS",counter)
    print("Time to find: ",(datetime.datetime.now() - start_time).total_seconds(), "sec")

    return result[0]

def sort_pieces_by_length(piece_dict):
    sorted_pieces = dict(sorted(piece_dict.items(), key=lambda item: len(item[1]),reverse=True))
    for piece_name, piece_coords in sorted_pieces.items():
        sorted_pieces[piece_name] = sorted(piece_coords, key=lambda coord: (coord[0], coord[1]))
    return sorted_pieces

def piece_already_placed(new_piece, pieces):
    for piece in pieces:
        if are_pieces_same(new_piece, piece):
            return True
    return False


def are_pieces_same(piece1, piece2):
    # Calculate the biases on x and y axes
    piece1 = [coord.copy() for coord in piece1]
    piece2 = [coord.copy() for coord in piece2]
    for coord1, coord2 in zip(piece1, piece2): # move to the positive quadrant
        coord1[0] += 10
        coord1[1] += 10
        coord2[0] += 10
        coord2[1] += 10

    piece1 = sorted(piece1, key=lambda coord: (coord[0], coord[1]))
    piece2 = sorted(piece2, key=lambda coord: (coord[0], coord[1]))

    bias_x = piece2[0][0] - piece1[0][0]
    bias_y = piece2[0][1] - piece1[0][1]

    # Check if all corresponding coordinates are the same with the calculated biases
    for coord1, coord2 in zip(piece1, piece2):
        if coord1[0] + bias_x != coord2[0] or coord1[1] + bias_y != coord2[1]:
            return False
    return True


print(solve(5, 12, {'F': [[0, 0], [1, 0], [1, -1], [1, 1], [2, 1]], 'W': [[0, 0], [1, 0], [1, 1], [2, 1], [2, 2]], 'V': [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]], 'X': [[0, 0], [1, 0], [-1, 0], [0, 1], [0, -1]], 'N': [[0, 0], [0, 1], [1, 1], [1, 2], [1, 3]], 'P': [[0, 0], [0, 1], [0, 2], [1, 1], [1, 2]], 'U': [[0, 0], [0, 1], [1, 0], [2, 0], [2, 1]], 'Z': [[0, 0], [1, 0], [1, -1], [1, -2], [2, -2]], 'I': [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]], 'Y': [[0, 0], [1, 0], [2, 0], [2, 1], [3, 0]], 'T': [[0, 0], [0, 1], [0, 2], [-1, 2], [1, 2]], 'L': [[0, 0], [0, 1], [1, 0], [0, 2], [0, 3]]}))

该求解器能找到正确解，但我希望在合理时间内获取全部解（或至少更多解）。我已尝试优化，但仍存在不必要的递归分支。根据维基百科，5×12的棋盘共有1010种解。我的实现找到第一个解需约22秒，递归调用次数达23000次，若要获取全部解耗时将超6小时。请问有哪些优化技术能让我在分钟级时间内获取全部解？

优化技术建议 #

• 预生成方块的唯一形态：现在每次回溯都实时旋转、翻转方块，还重复检查形态是否已放置，严重拖慢速度。可以提前为每个方块生成所有不重复的旋转、翻转形态，去重后存入列表。回溯时直接遍历预生成的形态，不用实时计算，也避免重复尝试相同形状。
• 优化放置顺序：当前按方块长度降序排序是正确方向，但可以进一步优先放置形状特殊、约束性强的方块（比如X形，它的旋转形态最少，放置后能快速缩小搜索空间）。把这类方块放在最前面，能更早剪枝无效分支，减少递归次数。
• 强化剪枝策略：
  • 改进find_smallest_area：不仅检查最小空白区域≥5，还要确保所有空白区域的面积都能被5整除（因为每个方块占5格），如果存在面积无法被5整除的空白区域，直接剪枝。
  • 实时计算剩余方块总面积，和当前空白区域总面积对比，不匹配则立即回溯。
• 优化棋盘表示：当前用二维列表存储字符，检查空位和放置/移除操作的效率较低。可以改用整数位掩码，5×12=60bit刚好能被Python的整数容纳。这样放置合法性检查、方块放置/移除都可以用位运算完成，速度提升显著。
• 对称性剪枝：棋盘存在旋转、翻转等对称性，会生成大量重复解。可以约束第一个方块的放置位置（比如固定在左上角区域），避免搜索对称的分支，同时减少重复解的生成。
• 简化回溯逻辑：
  • 移除多余的placed_pieces列表：回溯是按顺序处理方块，每个方块只会被放置一次，不需要记录已放置的形态。
  • 若要获取全部解，找到解后不要返回True，而是继续搜索，直到所有分支遍历完成。
• 提前过滤无效位置：对于每个方块形态，只计算能让整个方块落在棋盘内的起始坐标范围，不用遍历所有格子。比如宽度为3的方块，x坐标最大只能到width-3，减少循环次数。
• 缓存方块偏移量：预生成方块形态时，将坐标转换为以左上角为原点的偏移量，放置时直接计算绝对坐标，不用每次减去第一个坐标的偏移，减少计算开销。

内容的提问来源于stack exchange，提问作者Riomare