c++ - 使用回溯的代码骑士之旅没有显示任何输出

Question

这段代码没有给出任何输出。它应该输出一个 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";

}

Answer 1

替换以下代码:

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 才能得到结果。正如我猜到的那样，复杂性正在扼杀你。