C++递归骑士巡游问题排查：仅输出起始位无后续/无解提示

问题描述 #

我用C++递归实现骑士巡游，代码接近完成，但moveKnight函数存在问题。要求骑士在8*8棋盘上遍历每个格子仅一次，并输出到达每个格子的步数。目前代码仅输出起始位置board[0][0]=1，既无法继续遍历也不提示"No solution"，求排查方向。

原代码 #

#include <iostream>
using namespace std;
//Global Variables

//Defining the 8 possible Moves in the order from class
int yMove[8] = { 1,2, 2, 1,-1,-2,-2,-1 };
int xMove[8] = { 2,1,-1,-2,-2,-1, 1, 2 };

int board[8][8];
int startx, starty = 0;
int movecount = 1;

//checks if move is safe
bool checkSafe(int x, int y)
{
return (x >= 0 && x < 8 && y >= 0 && y < 8 && board[x][y] == 0);
}

//Prints Current board
void printBoard(int board[8][8])
{
for (int x = 0; x < 8; x++)
{
    for (int y = 0; y < 8; y++)
        cout << " " << board[x][y] << " ";
    cout << endl;
}
}

bool moveKnight(int x, int y, int movecount)
{
if (!checkSafe(x, y))
{
    board[x][y] = movecount;
    return true;
}
//end condition
if (movecount == 64)
    return true;
if (moveKnight(x + xMove[1], y + yMove[1], movecount + 1))
    return true;
else if (moveKnight(x + xMove[0], y + yMove[0], movecount + 1))
    return true;
else if (moveKnight(x + xMove[2], y + yMove[2], movecount + 1))
    return true;
else if (moveKnight(x + xMove[3], y + yMove[3], movecount + 1))
    return true;
else if (moveKnight(x + xMove[4], y + yMove[4], movecount + 1))
    return true;
else if (moveKnight(x + xMove[5], y + yMove[5], movecount + 1))
    return true;
else if (moveKnight(x + xMove[6], y + yMove[6], movecount + 1))
    return true;
else if (moveKnight(x + xMove[7], y + yMove[7], movecount + 1))
    return true;
else
{
    board[x][y] = 0;
    return false;
}
}

int KnightTour()
{
//creating board
for (int x = 0; x < 8; x++)
{
    for (int y = 0; y < 8; y++)
        board[x][y] = 0;
}
board[startx][starty] = 1;
movecount + 1;
//No possible moves
if (!moveKnight(startx, starty, movecount))
    cout << "Not possible";
else
{
    //yes possible now print
    printBoard(board);
}
//exits
return 0;
}

int main()
{
//calls knights tour
KnightTour();
cout << endl;
system("pause");
return 0;
}

错误分析 #

• 起始位置变量未正确初始化：int startx, starty = 0;仅初始化了starty，startx是未定义的垃圾值，会导致初始位置异常。
• moveKnight核心逻辑颠倒：开头的if (!checkSafe(x, y))判断完全错误，当前位置(x,y)是已放置步数的位置，此逻辑会让越界/已访问的位置被错误标记并终止递归。
• 终止条件位置错误：movecount == 64的判断被放在错误逻辑之后，导致无法正确触发遍历完成的终止条件。
• 无效语句：KnightTour中的movecount + 1;是无意义表达式，未对变量产生任何修改。
• 递归移动逻辑缺失安全检查：尝试下一步移动时未先验证目标位置是否安全，直接递归会导致无效路径大量触发。

修正后的代码 #

#include <iostream>
using namespace std;

// 定义骑士的8种可能移动方向
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };

int board[8][8];
int startx = 0, starty = 0; // 正确初始化起始位置

// 检查位置(x,y)是否在棋盘内且未被访问
bool checkSafe(int x, int y) {
    return (x >= 0 && x < 8 && y >= 0 && y < 8 && board[x][y] == 0);
}

// 打印棋盘（优化对齐效果）
void printBoard(int board[8][8]) {
    for (int x = 0; x < 8; x++) {
        for (int y = 0; y < 8; y++) {
            cout << (board[x][y] < 10 ? " " : "") << board[x][y] << " ";
        }
        cout << endl;
    }
}

bool moveKnight(int x, int y, int movecount) {
    // 终止条件：已完成64步遍历
    if (movecount == 64) {
        return true;
    }

    // 循环尝试所有8种移动方向
    for (int i = 0; i < 8; i++) {
        int nextX = x + xMove[i];
        int nextY = y + yMove[i];
        if (checkSafe(nextX, nextY)) {
            board[nextX][nextY] = movecount + 1;
            // 递归尝试下一步，成功则向上返回true
            if (moveKnight(nextX, nextY, movecount + 1)) {
                return true;
            }
            // 回溯：当前方向走不通，取消位置标记
            board[nextX][nextY] = 0;
        }
    }

    // 所有方向均无法走通，返回false
    return false;
}

int KnightTour() {
    // 初始化棋盘为0（未访问状态）
    for (int x = 0; x < 8; x++) {
        for (int y = 0; y < 8; y++) {
            board[x][y] = 0;
        }
    }
    board[startx][starty] = 1; // 标记起始位置为第1步

    if (!moveKnight(startx, starty, 1)) {
        cout << "Not possible" << endl;
    } else {
        printBoard(board);
    }
    return 0;
}

int main() {
    KnightTour();
    cout << endl;
    system("pause");
    return 0;
}

修正说明 #

1. 修复了起始位置变量的初始化问题，确保从(0,0)开始遍历。
2. 重构moveKnight函数逻辑：先判断遍历是否完成，再循环尝试所有移动方向，每一步先验证目标位置安全性，标记后递归，失败则回溯取消标记。
3. 删除无效语句，优化棋盘输出的对齐效果，提升可读性。

注意：纯递归的骑士巡游算法在8*8棋盘上运行速度较慢，因为路径组合过多。若要提升效率，可引入Warnsdorff规则（优先选择下一步可移动位置最少的方向），但这超出了基础递归练习的范畴。

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