针对非拼图类矩形谜题的回溯算法优化方案问询

我正在开发一款矩形谜题求解器（并非传统带凹凸的拼图块），之前询问适配的算法没得到理想方案，于是自己实现了一个基于回溯的算法。

算法概述 #

• 用一维数组表示谜题的最终布局
• 每个块存储与其他所有块的适应度值（用于衡量拼接匹配难度）
• 设定阈值（threshold），适应度值在此范围内的块视为可拼接

实现代码 #

def solve_image(self, col: int, state: list[Candidate], used_pieces: list[int]) -> list:

        threshold = 10
        print(f'Used pieces: {used_pieces}')
        self.counter = self.counter + 1

        # finishing condition
        if col > self.cols * self.rows - 1:
            print(f'Went over {self.counter} pieces')
            return state

        if col == 0:
            # randomly choose the first piece from all the pieces
            for piece in self.image_pieces:
                # first convert the piece to a candidate to be able to use it in the algorithm
                piece_to_candidate = Candidate(piece, fitness_value=0)
                result = self.solve_image(col=col + 1, state=[piece_to_candidate],
                                          used_pieces=[piece_to_candidate.piece.index])
                if len(result) > 0:
                    return result

            return []
        else:
            if col % self.cols == 0:
                # the piece is in the beginning of the row and therefore there is no piece before it in the row
                # take the first piece of the row before and go through the bottom candidates
                # the piece from which the candidates will be taken for the next piece
                candidate_piece = state[col - self.cols]
                sorted_candidates = candidate_piece.piece.get_sorted_candidates(Edge.BOTTOM)
                possible_candidates = list(filter(lambda x: x.fitness_value < threshold, sorted_candidates))
                for candidate in possible_candidates:
                    if candidate.piece.index not in set(used_pieces):
                        new_state = state + [candidate]
                        new_used = used_pieces + [candidate.piece.index]
                        result = self.solve_image(col=col + 1, state=new_state, used_pieces=new_used)
                        if len(result) > 0:
                            return result
                return []
            else:
                # the piece is somewhere in the image where it always has a piece before it
                # the piece from which the candidates will be taken for the next piece
                candidate_piece = state[col - 1]
                sorted_candidates = candidate_piece.piece.get_sorted_candidates(Edge.RIGHT)
                possible_candidates = list(filter(lambda x: x.fitness_value < threshold, sorted_candidates))
                for candidate in possible_candidates:
                    if candidate.piece.index not in set(used_pieces):
                        # check if the piece is in a different row than the first one, if yes, compare more edges
                        passes_top_edge = True
                        if col > self.cols:
                            top_edge = state[col - self.cols]
                            for edge_candidate in top_edge.piece.get_sorted_candidates(Edge.BOTTOM):
                                if edge_candidate.fitness_value > threshold:
                                    passes_top_edge = False
                                    break
                                if edge_candidate.piece.index == candidate.piece.index:
                                    break
                                passes_top_edge = False

                        if passes_top_edge:
                            new_state = state + [candidate]
                            new_used = used_pieces + [candidate.piece.index]
                            result = self.solve_image(col=col + 1, state=new_state, used_pieces=new_used)
                            if len(result) > 0:
                                return result
                return []

当前问题 #

这段代码会根据筛选条件遍历所有可选块，逐个放入谜题中，通过判断块在谜题中的位置（首块、行首、中间位置）检查对应边缘的匹配度，直到完成整个谜题。算法在6x8这类小尺寸谜题上表现正常，但处理更大尺寸的谜题时耗时极长，求优化该回溯算法的具体思路。

优化思路 #

1. 强化剪枝与预处理 #

• 提前生成精简候选集：不要等到回溯时才过滤候选块，预处理阶段就为每个块的每个边缘生成仅包含适应度低于阈值的候选列表，并按适应度从小到大排序。优先尝试匹配度最高的块，能更早找到可行解，大幅减少无效分支的探索。
• 完善双向匹配检查：当前处理中间块时，仅验证了顶部块的底部候选是否包含当前块，改为同时检查当前块的顶部边缘与顶部块的底部边缘的适应度是否符合阈值，提前排除不符合的候选，避免无效递归。

2. 数据结构优化 #

• used_pieces改用集合存储：当前每次判断candidate.piece.index not in set(used_pieces)都会重新生成集合，直接将used_pieces初始化为集合，添加/移除元素时直接操作集合，查询时间从O(n)降至O(1)，减少大量耗时。
• 缓存适应度计算结果：如果适应度计算是耗时操作，提前将所有块间的适应度值缓存到二维数组中，避免回溯过程中重复计算。

3. 回溯策略优化 #

• 启发式候选排序：遍历候选块时，优先选择适应度值最小（匹配度最高）的块，这种启发式搜索能快速逼近可行解，减少不必要的分支探索。
• 迭代实现回溯：递归回溯在谜题尺寸较大时会产生栈开销，改用迭代方式实现回溯，手动管理状态栈，既避免递归深度限制，也能更灵活地控制搜索过程。
• 对称性剪枝：如果谜题存在旋转、翻转等对称性，固定首块的位置或方向，避免重复搜索对称的解空间，缩小搜索范围。

4. 并行化探索 #

• 对于首块的选择，可以并行尝试不同的首块，每个首块对应一个独立的搜索分支，利用多核CPU的算力加速搜索过程。

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