如何开发高效启发式求解200×200马踏棋盘？排查现有代码问题

问题背景 #

需求为开发启发式算法，以最短时间求解马踏棋盘问题，需支持200×200规模矩阵并秒级输出结果。现有Python代码无法正常运行，需排查问题并优化效率。

代码问题排查 #

1. 访问状态检查效率极低 #

原代码使用[a, b] not in ruta判断位置是否已访问，ruta是列表结构，每次检查的时间复杂度为O(n)（n为当前路径长度）。对于200×200的棋盘，n最大可达40000，这会导致单次检查耗时剧增，整体时间复杂度爆炸。

2. 内存占用过高 #

每次生成子路径时，通过ruta + [[a, b]]复制整个路径列表。200×200规模下，单个路径包含40000个坐标元素，栈中存储大量此类复制路径会直接耗尽内存，导致程序无响应或崩溃。

3. 迭代DFS的无效存储 #

原代码的栈中存储完整路径，而非仅当前状态信息，进一步加剧了内存消耗，且没有高效的回溯机制。

优化方案 #

核心优化点 #

• 用二维数组记录访问状态：将访问判断从O(n)降至O(1)。
• 回溯式路径维护：使用单个列表存储路径，通过添加/删除元素实现回溯，避免路径复制。
• 优化Warnsdorff规则计算：预计算马的走法，减少重复循环；按后续可选步数升序排序（Warnsdorff核心规则），优先选择后续走法更少的位置，减少无效搜索。
• 迭代DFS的状态精简：栈中仅存储当前位置、处理标记，通过回溯复用访问矩阵和路径，避免冗余存储。

优化后代码 #

import sys
sys.setrecursionlimit(1 << 25)

def main():
    Fil, Col, ii, jj = map(int, input().split())
    # 马的8种走法
    moves = [(-2, -1), (-1, -2), (1, -2), (2, -1),
             (2, 1), (1, 2), (-1, 2), (-2, 1)]
    
    # 初始化访问矩阵和路径
    visited = [[False for _ in range(Col)] for _ in range(Fil)]
    path = []
    total_cells = Fil * Col
    
    # Warnsdorff规则：计算当前位置的后续可选步数
    def get_valid_moves(x, y):
        valid = []
        for dx, dy in moves:
            nx, ny = x + dx, y + dy
            if 0 <= nx < Fil and 0 <= ny < Col and not visited[nx][ny]:
                # 计算该位置的后续可选步数
                count = 0
                for dx2, dy2 in moves:
                    nnx, nny = nx + dx2, ny + dy2
                    if 0 <= nnx < Fil and 0 <= nny < Col and not visited[nnx][nny]:
                        count += 1
                valid.append((count, nx, ny))
        # 按后续步数升序排序（Warnsdorff核心）
        valid.sort()
        return [(nx, ny) for _, nx, ny in valid]
    
    # 迭代DFS实现回溯
    stack = [(ii, jj, False)]
    while stack:
        x, y, processed = stack.pop()
        if processed:
            # 回溯：标记未访问，移除路径
            visited[x][y] = False
            path.pop()
            continue
        
        if visited[x][y]:
            continue
        
        # 标记已访问，加入路径
        visited[x][y] = True
        path.append((x, y))
        
        if len(path) == total_cells:
            # 找到完整路径，输出结果
            matrix = [[0]*Col for _ in range(Fil)]
            for idx, (a, b) in enumerate(path, 1):
                matrix[a][b] = idx
            # 打印矩阵
            for row in matrix:
                print(" ".join(f"{num:04d}" for num in row))
            return
        
        # 标记为已处理，先压回栈
        stack.append((x, y, True))
        # 按Warnsdorff顺序压入子节点（栈是后进先出，反转顺序保证正确遍历）
        for nx, ny in reversed(get_valid_moves(x, y)):
            stack.append((nx, ny, False))
    
    # 200×200为偶数格棋盘，理论必有解，此处为容错输出
    print("无解")

if __name__ == "__main__":
    main()

优化效果说明 #

• 访问判断：从O(n)降至O(1)，大幅减少单步耗时。
• 内存消耗：仅维护单个路径和访问矩阵，内存占用从O(n²)降至O(n)（n为棋盘规模）。
• 搜索效率：Warnsdorff规则优先选择后续走法少的位置，直接避免大量无效搜索，200×200规模可实现秒级输出。

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