使用栈实现骑士巡游的C++程序遇无限循环求助

嘿，我来帮你排查骑士巡游程序无限循环的问题！你的代码看起来没贴完整（check_if_valid函数写到一半就断了），不过基于栈实现骑士巡游的常见坑，我整理了几个最可能的原因和修复思路：

1. 遗漏已访问位置的标记 #

骑士巡游绝对不能重复踩同一个格子，要是没记录哪些位置已经走过，程序大概率会在几个格子之间来回跳转，直接陷入死循环。

• 你需要加一个和棋盘大小匹配的二维数组，比如bool visited[8][8] = {false};，每次走到新位置就把对应格子标记为true。
• 重点：回溯的时候（也就是从栈里弹出当前位置时），一定要把这个格子的visited改回false，不然回溯后没法重新访问这个位置，要么卡死要么触发循环。

2. check_if_valid函数逻辑不完整/错误 #

从你贴的代码片段看，这个函数只写了一半，它必须同时满足两个条件才算合法移动：

• 目标位置在棋盘范围内（比如国际象棋是8x8，所以要判断row >=0 && row <8 && col >=0 && col <8）
• 目标位置还没被访问过（结合上面的visited数组）
  要是这个函数漏了任何一个判断，程序要么尝试走到棋盘外，要么重复走同一个格子，直接引发循环。

3. 栈回溯逻辑出错 #

用栈实现骑士巡游本质是深度优先搜索（DFS），如果回溯时没正确处理栈的状态和访问标记，很容易出问题：

• 比如你可能把所有可能的移动都压入栈，但没判断是否已经走完所有格子，导致一直在无效路径里打转。
• 正确的逻辑应该是：每次取出栈顶的当前位置，尝试所有8种骑士移动，找到第一个合法且未访问的位置，标记后压入栈；如果所有移动都无效，就弹出当前位置，取消访问标记（回溯），继续尝试上一个位置的下一种移动。

4. 缺少终止条件 #

程序必须有明确的终止信号：当栈的大小等于棋盘总格子数（比如8x8的64）时，说明已经完成巡游，应该立刻终止程序。要是没这个判断，程序找到解后还会继续瞎逛，甚至陷入循环。

给你补了一段可以参考的核心代码，你可以对照自己的代码调整：

#include <iostream>
#include <stack>
#include <cstdlib>
using namespace std;

const int BOARD_SIZE = 8;
bool visited[BOARD_SIZE][BOARD_SIZE] = {false};

struct whereIam {
    int row, col;
    int moveIndex; // 记录当前已尝试到第几种移动，回溯时不用从头再来
};

// 骑士的8种L形移动
int Lrow[8] = {1, 1, 2, 2, -1, -1, -2, -2};
int Lcol[8] = {2, -2, 1, -1, 2, -2, 1, -1};

bool check_if_valid(int row, int col) {
    // 同时检查边界和是否已访问
    return (row >= 0 && row < BOARD_SIZE && col >= 0 && col < BOARD_SIZE && !visited[row][col]);
}

int main() {
    stack<whereIam> path;
    // 从(0,0)开始巡游，可自行修改起始位置
    whereIam start = {0, 0, 0};
    path.push(start);
    visited[0][0] = true;

    while (!path.empty()) {
        whereIam current = path.top();
        path.pop();

        // 检查是否完成巡游
        if (path.size() + 1 == BOARD_SIZE * BOARD_SIZE) {
            cout << "巡游完成！路径已找到" << endl;
            // 这里可以添加路径打印逻辑（栈是逆序的，建议转存到数组再输出）
            return 0;
        }

        // 尝试当前位置未试过的移动
        bool foundNext = false;
        for (int i = current.moveIndex; i < 8; i++) {
            int newRow = current.row + Lrow[i];
            int newCol = current.col + Lcol[i];
            if (check_if_valid(newRow, newCol)) {
                // 把当前位置重新压栈，下次从下一个移动开始尝试
                current.moveIndex = i + 1;
                path.push(current);
                // 压入新位置
                whereIam nextPos = {newRow, newCol, 0};
                path.push(nextPos);
                visited[newRow][newCol] = true;
                foundNext = true;
                break;
            }
        }

        // 没找到合法移动，回溯取消标记
        if (!foundNext) {
            visited[current.row][current.col] = false;
        }
    }

    // 栈空还没找到解（理论上8x8棋盘任意起始都有解，大概率是代码还有问题）
    cout << "未找到有效巡游路径" << endl;
    return 0;
}

• 可以在循环里加一些调试输出，比如每次压栈/弹栈时打印当前位置，看看是不是在几个固定格子之间来回跳，这样能快速定位循环的源头。
• 如果想加快搜索速度，可以试试Warnsdorff规则（优先选择可移动步数最少的格子），能大幅减少无效搜索，避免长时间卡滞。

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