You need to enable JavaScript to run this app. 使用C++实现骑士巡游(Knight's Tour)出现无限循环问题求助
优惠活动
大模型
产品
解决方案
定价
更多

使用C++实现骑士巡游(Knight's Tour)出现无限循环问题求助

骑士巡游代码问题排查与修复

核心问题1:传值导致回溯失效

你当前的knightMove函数中chess参数采用值传递,每次递归调用都会生成独立的棋盘副本,你在函数内对棋盘的赋值、回溯时的重置操作都只会作用于当前副本,不会影响上层递归的棋盘数据,不仅回溯逻辑完全不生效,还会产生大量无效递归分支,直接导致程序卡死看起来像无限循环。
修复方式:将参数改为引用传递,修改函数声明为void knightMove(int x, int y, vector<vector<int>>& chess, int moves)。

核心问题2:暴力搜索效率过低

即使修复了传值问题,纯暴力回溯搜索8*8棋盘的骑士巡游路径的时间复杂度是指数级的,搜索空间过于庞大,正常需要数小时甚至更久才能跑出结果,需要加入Warnsdorff启发式规则优化:每次选择下一步移动时,优先走后续可选走法最少的格子,可以把搜索耗时压缩到毫秒级。

修复后完整可运行代码

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

// 计算当前位置(x,y)下一步可选的有效走法数量
int countAvailable(int x, int y, vector<vector<int>>& chess) {
    int dx[] = {2,2,-2,-2,1,1,-1,-1};
    int dy[] = {1,-1,1,-1,2,-2,2,-2};
    int cnt = 0;
    for(int k=0; k<8; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if(nx>=0 && nx<8 && ny>=0 && ny<8 && chess[nx][ny]==-1) cnt++;
    }
    return cnt;
}

// 改为bool返回值,找到解直接返回终止递归
bool knightMove(int x, int y, vector<vector<int>>& chess, int moves) {
    chess[x][y] = moves;
    if(moves == 63) {
        for(int p=0; p<8; p++) {
            for(int q=0; q<8; q++) {
                cout << chess[p][q] << "\t";
            }
            cout << endl;
        }
        return true;
    }
    int dx[] = {2,2,-2,-2,1,1,-1,-1};
    int dy[] = {1,-1,1,-1,2,-2,2,-2};
    // 存储可选的下一步:{可选走法数量, x, y}
    vector<pair<int, pair<int, int>>> nextSteps;
    for(int k=0; k<8; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if(nx>=0 && nx<8 && ny>=0 && ny<8 && chess[nx][ny]==-1) {
            int cnt = countAvailable(nx, ny, chess);
            nextSteps.push_back({cnt, {nx, ny}});
        }
    }
    // 按可选走法数量从小到大排序,遵循Warnsdorff规则
    sort(nextSteps.begin(), nextSteps.end());
    for(auto& step : nextSteps) {
        int nx = step.second.first, ny = step.second.second;
        if(knightMove(nx, ny, chess, moves+1)) {
            return true;
        }
    }
    // 回溯重置
    chess[x][y] = -1;
    return false;
}

int main() {
    vector<vector<int>> chess(8, vector<int>(8, -1));
    knightMove(0, 0, chess, 0);
    return 0;
}

修复说明

  • 采用引用传递棋盘,回溯逻辑可以正确作用于同一个棋盘对象,避免了无意义的副本拷贝开销
  • 加入Warnsdorff启发式规则,大幅缩小搜索范围,运行后可以立即输出合法的巡游路径
  • 增加bool返回值,找到第一个解就直接终止递归,不需要继续搜索其他解

内容的提问来源于stack exchange,提问作者Sridev

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.18 07:54:07