Python回溯法实现骑士巡游问题：代码异常问题求助

核心问题分析 #

你的代码存在三个关键问题，导致输出不符合预期且大棋盘运行效率极低：

1. 结果引用错误 #

找到完整解时，result.append(board)添加的是棋盘对象的引用而非副本。后续回溯修改棋盘时，已存入结果列表的所有棋盘会被同步修改，最终结果全是回溯后的未完成状态。

2. 回溯状态恢复逻辑错误 #

状态恢复代码（重置棋盘和坐标）的缩进错误：即使当前移动不合法（执行了continue），仍会执行坐标回退操作，破坏current_x和current_y的正确值，引发后续移动的坐标混乱。

3. 无搜索优化，大棋盘效率极低 #

纯递归回溯的搜索空间随棋盘规模指数级增长，对于n=8的棋盘，暴力搜索几乎无法在合理时间内找到解，必须引入启发式优化。

修复后的代码 #

def knight(n):
    xy_movements = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(-1,2),(1,-2),(-1,-2)]
    board = [["."]*n for _ in range(n)]
    board[0][0] = 0
    current_x = 0
    current_y = 0
    result = []

    def backtrack(num):    
        nonlocal current_x, current_y
        if num == (n*n)-1:
            # 添加棋盘深拷贝，避免引用修改
            result.append([row.copy() for row in board])
            return
        
        for move in xy_movements:
            new_x = current_x + move[0]
            new_y = current_y + move[1]
            if 0 <= new_x < n and 0 <= new_y < n and board[new_x][new_y] == ".":
                # 执行移动并标记
                current_x, current_y = new_x, new_y
                board[current_x][current_y] = num + 1
                backtrack(num + 1)
                # 仅当执行了移动才进行状态恢复
                board[current_x][current_y] = "."
                current_x -= move[0]
                current_y -= move[1]

    backtrack(0)
    return result

关键修复点说明 #

• 深拷贝结果：用[row.copy() for row in board]创建棋盘副本存入结果，避免后续修改影响已记录的解。
• 修正缩进：将状态恢复代码移入合法移动的if块内部，确保只有执行过移动操作才回退状态，避免坐标混乱。
• 提前计算新坐标：减少重复计算，提升代码可读性。

大棋盘优化建议 #

对于n≥5的棋盘，纯回溯效率极低，建议引入Warnsdorff规则优化搜索顺序：每次优先选择下一步可移动位置最少的方向，大幅减少无效搜索分支。示例优化逻辑：

def get_sorted_moves(x, y, board, n, movements):
    candidates = []
    for dx, dy in movements:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == ".":
            # 计算该候选位置的下一步可选数量
            count = 0
            for ddx, ddy in movements:
                nnx = nx + ddx
                nny = ny + ddy
                if 0 <= nnx < n and 0 <= nny < n and board[nnx][nny] == ".":
                    count += 1
            candidates.append((count, dx, dy))
    # 按可选数量升序排序，优先选择分支少的方向
    candidates.sort()
    return [(dx, dy) for _, dx, dy in candidates]

在回溯函数的循环中，用get_sorted_moves(current_x, current_y, board, n, xy_movements)替代原有的xy_movements，可大幅提升n=8时的搜索效率。

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