1

そこで、8*8 のチェス盤のナイツ ツアーを解決するために、この実装を思いつきました。しかし、実行に長い時間がかかっているようです (停止しなければならないほど長い)。しかし、dx、dy 配列をコメントに書かれているものに置き換えると、プログラムは魔法のように機能し、出力が得られます。ブルートフォースアルゴリズムが解決策を迅速に見つけることができるように、配列を巧みに選択していると彼らは言います。

しかし、そもそもこの配列 (dx,dy) は、他のコードから取得したものです。では、なぜこのコードがそれらの配列 (コメント内) で機能し、私のものではないのか、誰でも説明できます。

#include <cstdio>

using namespace std;

int dx[8] = {  1,  1, 2,  2,  -1, -1, -2, -2};
int dy[8] = {  2, -2, 1, -1,  2,  -2,  1, -1};

//int dx[8] = {  2, 1, -1, -2, -2, -1,  1,  2 };
//int dy[8] = {  1, 2,  2,  1, -1, -2, -2, -1 };

bool solve(bool arr[8][8],int x,int y,int moves){
    if(moves==0)return true;
    if(x<0 || y<0 || x>7 || y>7 || arr[x][y])return false;
    arr[x][y]=1;

    for(int i=0;i<8;i++)
        if(solve(arr,x+dx[i],y+dy[i],moves-1)){
            printf(" (%d,%d) ",x,y);
            return 1;
        }
    arr[x][y]=0;
    return false;
}

int main()
{
    bool arr[8][8];
    for(int i=0;i<8;i++)    for(int j=0;j<8;j++)    arr[i][j]=0;
    solve(arr,0,0,64);
    puts("");
}
4

2 に答える 2

0

チェスには 8 つの有効なナイトの動きがあります。

ナイターの動き

2 つの配列には、これら 8 つの移動がリストされています。

コードの 2 つのバージョンは、異なる順序で移動を試みます。たまたま、あるバージョンが他のバージョンよりもはるかに早く有効なソリューションに遭遇することがあります。

それだけです。

于 2014-02-02T14:34:20.830 に答える