Python递归回溯法求解骑士巡游问题：仅执行5步未进入递归判定

看起来你在骑士巡游的递归回溯实现上踩了几个常见的坑，导致程序提前卡壳，还触发不到结束条件。我帮你拆解问题并给出修复方案：

核心问题分析 #

从你给出的代码片段来看，主要有三个关键问题：

1. 缺少新位置合法性检查：遍历骑士的8个跳跃方向时，你没有判断新坐标是否在矩阵范围内，也没检查该位置是否已经被访问过——这会导致数组越界或者重复访问无效位置。
2. 没有回溯操作：递归回溯的核心是“走不通就回头”，如果当前路径走死了，你需要把当前位置的标记重置回初始状态，否则后续的递归分支会误以为这个位置已经被占用，无法继续探索。
3. 结束条件可能不匹配：如果你的步数nr是从0开始计数的，那nr == matrix_len*matrix_len -1是对的（比如5x5矩阵总共有25个位置，0到24）；但如果nr从1开始，这个条件就永远满足不了，得改成nr == matrix_len*matrix_len。

修复后的完整代码 #

下面是补全并修复后的代码，以5x5矩阵（预期24步，从0开始计数）为例：

JUMP_POS = [ (2,1), (2,-1), (1,2), (1,-2), (-1,2), (-1,-2), (-2,1), (-2,-1) ]

def springen(x, y, nr, matrix):
    matrix_len = len(matrix)
    # 标记当前位置为第nr步
    matrix[x][y] = nr
    
    # 检查是否完成巡游：当前步数等于总位置数-1（nr从0开始）
    if nr == matrix_len * matrix_len - 1:
        print("找到有效路径：")
        for row in matrix:
            print(row)
        return True
    
    # 遍历所有可能的跳跃方向
    for pos in JUMP_POS:
        xNeu = x + pos[0]
        yNeu = y + pos[1]
        # 核心：检查新位置是否合法（在矩阵内+未被访问）
        if 0 <= xNeu < matrix_len and 0 <= yNeu < matrix_len and matrix[xNeu][yNeu] == -1:
            # 递归尝试该位置，如果成功就直接返回
            if springen(xNeu, yNeu, nr + 1, matrix):
                return True
    
    # 回溯：所有方向都走不通，重置当前位置为未访问状态
    matrix[x][y] = -1
    return False

# 初始化5x5矩阵，用-1表示未访问的位置
if __name__ == "__main__":
    size = 5
    knight_matrix = [[-1 for _ in range(size)] for _ in range(size)]
    # 从(0,0)位置开始，第0步
    springen(0, 0, 0, knight_matrix)

关键修复点说明 #

• 合法性检查：新增的条件确保骑士只会跳到矩阵内的空白位置，避免了无效的递归调用和数组越界错误。
• 回溯操作：在所有递归分支失败后，把当前位置重置为-1，这样其他路径尝试时还能再次使用这个位置——这是你之前代码缺失的核心逻辑，也是导致程序提前卡壳的主要原因。
• 结束条件对齐：代码里默认nr从0开始计数，如果你习惯从1开始，只需要把结束条件改成nr == matrix_len * matrix_len，同时初始调用时nr传1即可。

运行这段代码后，程序会正确递归探索所有可能路径，直到找到完整的24步巡游矩阵。

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