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 秒後に良い結果が得られました。(「ゼロ」が 3 つしか残っていないフィールド。) したがって、全体的なアルゴリズムは機能します。

出力の見栄えを良くするためのヒント:

#include <iomanip>

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

をバンプすると、ランタイムが 2.5 秒に増加し、フィールドには 2 つのゼロしかありませんでした62。実行が終了する63のをまだ待っています。64

編集: 30 分後、64実行はまだ終了していません。ポイントを作りました。

あなたの問題はプログラムではなく、アルゴリズムです。結果を得るには、何兆回もの動きを経る必要があります。私が推測したように、複雑さはあなたを殺しています。

于 2015-06-16T14:02:26.997 に答える