这段代码没有给出任何输出。它应该输出一个 8X8 大小的矩阵。
#include <iostream>
#define N 8
using namespace std;
此函数打印矩阵:
void print(int arr[][N]){
int i, j;
for (i = 0; i < N; i++){
for (j = 0; j < N; j++)
cout<<arr[i][j]<<" ";
cout<<endl;
}
}
此函数检查 x 和 y 的限制以及骑士是否已经访问过那个地方。
bool safe(int x, int y, int arr[][N]){
if(x>=0 && y>=0 && x<N && y<N && arr[x][y] == 0){
return true;
}
return false;
}
这个函数做大部分事情:
bool solveKT(int x, int y, int movei, int arr[][N], int xmove[], int ymove[] ){
if(movei == (N*N)+1){
return true;
}
for(int k=0 ; k<8 ; k++){
int nextx = x + xmove[k];
int nexty = y + ymove[k];
if(safe(nextx, nexty, arr) == true){
arr[nextx][nexty] = movei;
if(solveKT(nextx, nexty, movei+1, arr, xmove, ymove) == true){
return true;
}
arr[nextx][nexty] = 0; // backtrack
}
}
return false;
}
这只是一个驱动函数:
int main(){
int arr[N][N]={0};
int xmove[] = {1, 1,2, 2,-1,-1,-2,-2};
int ymove[] = {2,-2,1,-1, 2,-2, 1,-1};
arr[0][0] = 1;
int movei = 2;
bool a = solveKT(0, 0, movei, arr, xmove, ymove);
if(a == true){
print(arr);
}
else
cout<<"no solution";
}
最佳答案
替换以下代码:
if(movei == (N*N)+1){
return true;
}
...具有硬编码值...
if(movei == 62){
return true;
}
...在 0.1 秒后给了我一个很好的结果。 (一个字段只剩下三个“零”。)因此您的整体算法有效。
关于更好看的输出的提示:
#include <iomanip>
cout << setw(3) << arr[i][j];
将 62
增加到 63
将运行时间增加到 2.5 秒,字段上只有两个零。仍在等待 64
运行完成。
编辑:半小时后,64
运行仍未完成。点了。
你的问题不是程序,你的问题是算法。它必须经过数万亿次 Action 才能得到结果。正如我猜到的那样,复杂性正在扼杀你。
关于c++ - 使用回溯的代码骑士之旅没有显示任何输出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30863247/