使用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
相关产品推荐
相关产品推荐

