骑士巡游暴力算法：递归回溯的回溯深度困惑求解

嘿，我完全懂你这种困惑——骑士巡游的递归回溯确实容易让人绕晕，尤其是搞不清到底回溯到哪一步才能继续往下推进。咱们一点点拆解这个问题，结合递归栈的本质来理清楚：

首先得明确：递归调用的每一次执行，都会在内存里创建一个栈帧——这个栈帧里保存了当前函数的所有状态：比如当前骑士的位置、已经走了多少步、棋盘的访问状态（如果是通过参数传递的话）。回溯的过程，本质就是栈帧依次弹出的过程，而弹出的深度完全由「当前路径是否走进死胡同」决定。

1. 什么时候触发回溯？ #

拿骑士巡游的暴力递归来说，每个栈帧会做这些事：

• 先检查是否已经走完所有格子（基例）：如果是，直接返回true，表示找到有效路径。
• 遍历骑士所有可能的8个移动方向，逐个尝试：
  • 对每个合法的下一步（在棋盘内且未被访问），标记该位置为已访问，然后递归调用自身，尝试从这个新位置继续走。
  • 如果这个递归调用返回false，说明从这个新位置出发，无论怎么都走不完整个棋盘——这时候就触发回溯：取消这个新位置的访问标记，然后回到循环，尝试当前位置的下一个方向。
• 如果当前位置的所有8个方向都试过了，还是走不通，就返回false，让上一层栈帧知道「从你那个位置走到我这里是死路」，上一层就会继续它的回溯流程。

2. 回溯的深度怎么确定？ #

这个深度完全是动态的，没有固定值：

• 如果你走到第10步发现所有下一步都走不通，就会回溯到第9步，尝试第9步的下一个未选方向；
• 如果第9步的所有方向都试过还是不行，就继续回溯到第8步；
• 以此类推，直到找到某一步还有没尝试过的方向，或者一路回溯到起点（这时候说明整个棋盘没有合法的巡游路径）。

举个简单的例子：假设你在5x5棋盘上走，第7步的时候走进了一个角落，周围所有格子要么出界要么已经走过。这时候第7步的递归会返回false，回到第6步的栈帧，第6步就会取消第7步的标记，然后尝试第6步的下一个方向。如果第6步的所有方向都试过还是不行，就继续回退到第5步，直到找到能继续走的分支。

结合代码片段理解（补全常见暴力实现逻辑） #

你提到的代码大概是类似这样的（我补全了关键部分）：

#include <vector>
#include <iostream>
using namespace std;

// 检查位置是否合法（在棋盘内且未被访问）
bool isValid(int row, int col, vector<vector<int>>& board) {
    int n = board.size();
    return row >= 0 && row < n && col >=0 && col < n && board[row][col] == 0;
}

bool knightTour(int row, int col, int moveCount, vector<vector<int>>& board) {
    int n = board.size();
    // 基例：所有格子都走完了，找到解
    if (moveCount == n * n) {
        // 打印棋盘
        for (auto& r : board) {
            for (int val : r) cout << val << " ";
            cout << endl;
        }
        return true;
    }

    // 骑士的8个移动方向
    int dirs[8][2] = {{-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}};

    // 遍历所有可能的下一步
    for (int i = 0; i < 8; i++) {
        int newRow = row + dirs[i][0];
        int newCol = col + dirs[i][1];
        if (isValid(newRow, newCol, board)) {
            // 标记当前位置为已访问（记录步数）
            board[newRow][newCol] = moveCount + 1;
            // 递归尝试下一步
            if (knightTour(newRow, newCol, moveCount + 1, board)) {
                return true; // 找到解就一路返回true
            }
            // 回溯：取消标记，因为当前方向走不通
            board[newRow][newCol] = 0;
        }
    }

    // 所有方向都试完了，走不通，返回false
    return false;
}

int main() {
    int n = 8; // 8x8棋盘
    vector<vector<int>> board(n, vector<int>(n, 0));
    board[0][0] = 1; // 从(0,0)出发，第一步标记为1
    knightTour(0, 0, 1, board);
    return 0;
}

这里的回溯关键就是board[newRow][newCol] = 0这行：当递归调用返回false时，说明这个方向是死路，所以把这个位置改回未访问状态，让上一步可以尝试其他方向。

小建议：可视化栈帧帮你理解 #

如果还是觉得绕，你可以手动模拟小棋盘（比如3x3或4x4）的递归过程：每调用一次递归就写一行当前的位置和步数，遇到返回false就划掉这一行，回到上一行继续。这样能直观看到栈帧的弹出（回溯）过程，以及每次回溯的深度。

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