1

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

}
4

1 回答 1

1

替换以下代码：

if(movei == (N*N)+1){
    return true;
}

...带有硬编码的值...

if(movei == 62){
    return true;
}

...在 0.1 秒后给了我一个很好的结果。（一个只剩下三个“零”的字段。）所以你的整体算法有效。

提示以获得更好的输出外观：

#include <iomanip>

cout << setw(3) << arr[i][j];

62将运行时间增加到632.5 秒，场上只有两个零。仍在等待64运行结束。

编辑：半小时后，64运行仍然没有完成。点了。

你的问题不是程序，你的问题是算法。它必须经过数万亿步才能得到结果。正如我猜想的那样，复杂性正在杀死你。

于 2015-06-16T14:02:26.997 回答