0

これが私が書いたコードです。

#include "genlib.h"
#include <iostream>
#include <math.h>
#include "vector.h"

struct square
{
    int x;
    int y;

};


bool knighttour(square start,int &counter,int cb[][8]);
Vector <square> generatemoves (square start);
void Marksquare(int &cb,int ctr);
void Unmarksquare(int &cb);
bool IsLegal(square a,int cb[][8]);




int main() 
{
    int chessboard[8][8];

    for (int i=0;i<8;i++)
        for (int j=0;j<8;j++)
            chessboard[i][j]=-1;

    int counter=1;

    for (int i=0;i<8;i++){
        for (int j=0;j<8;j++){
            square temp;
            temp.x=i;
            temp.y=j;
            if (knighttour(temp,counter,chessboard))
            {
                for (int k=0;k<8;k++){
                    cout<<chessboard[k][0]<<chessboard[k][1]<<chessboard[k][2]<<chessboard[k][3]<<chessboard[k][4]<<chessboard[k][5];
                    cout<<chessboard[k][6]<<chessboard[k][7]<<endl;}


            }

        }
    }


    return 0;
}


bool knighttour(square pt,int &counter,int cb[][8])
{

    Marksquare(cb[pt.x][pt.y],counter);
    if (counter==64)
        return true;

    counter++;

    Vector <square> temp = generatemoves(pt);

    for (int i=0;i<temp.size();i++)
    {
        if (IsLegal(temp[i],cb))
            knighttour(temp[i],counter,cb);
    }

    Unmarksquare(cb[pt.x][pt.y]);
    counter--;
    return false;

}



Vector <square> generatemoves (square start)
{
    Vector <square> temp;
    Vector <square> temp2;

        square mv1;
        mv1.x=start.x+2;
        mv1.y=start.y+1;
        temp.add(mv1);

        square mv2;
        mv2.x=mv1.x;
        mv2.y=start.y-1;
        temp.add(mv2);


        square mv3;
        mv3.y=start.y+2;
        mv3.x=start.x+1;
        temp.add(mv3);

        square mv4;
        mv4.y=start.y+2;
        mv4.x=start.x-1;
        temp.add(mv4);

        square mv5;
        mv5.x=start.x-2;
        mv5.y=start.y+1;
        temp.add(mv5);

        square mv6;
        mv6.x=start.x-2;
        mv6.y=start.y-1;
        temp.add(mv6);

        square mv7;
        mv7.y=start.y-2;
        mv7.x=start.x-1;
        temp.add(mv7);

        square mv8;
        mv8.y=start.y-2;
        mv8.x=start.x+1;
        temp.add(mv8);


        for (int i=0;i<temp.size();i++)
            if (temp[i].x>=0 && temp[i].x<=7 && temp[i].y>=0 && temp[i].y<=7)
                temp2.add(temp[i]);




        return temp2;
}



void Marksquare(int &a,int ctr)
{
    a=ctr;

}



void Unmarksquare(int &a)
{
    a=-1;
}


bool IsLegal(square a,int cb[][8])
{
    if (cb[a.x][a.y]==-1)
        return true;
    else 
        return false;
}

少し説明。私はチェスのボードを表すために int [8][8] を使用しており、最初はボードのすべての正方形に数字 -1 を入れています。

ナイトが移動すると、カウンター (int カウンター) で訪問するマスをマークし、そこから (そしてナイトが実行できるすべての正当な動きに対して) パスを見つけるために再帰呼び出しを行います (目標は、各マスを 1 回だけ訪問することです)。 ）。

カウンターが 64 に達すると、関数bool knighttour(square start,int &counter,int cb[][8]) は true を返す必要があり、メイン プログラムは [8][8] チェス盤にマークされているように「騎士のツアー」を表示する必要があります。

私が提供した上記のコードは無限ループで実行されると思います。3分間走らせました。

4

3 に答える 3

3

理論によると：

...徹底的なブルートフォースアプローチ（すべての可能な移動シーケンスを繰り返すアプローチ）は、ナイトツアーの問題には決して適用できないことに注意することが重要です（非常に小さいボードサイズを除く）。通常の8x8チェス盤の場合、約4x1051の可能な移動シーケンスがあり[9]、このような多数の移動を繰り返すには計り知れない時間がかかります。

したがって、プログラムが確実に機能するようにするには、ボードサイズを小さくしてみてください（たとえば4x4）。

プログラムが妥当な時間内に8x8で動作するようにするには、アルゴリズムを変更する必要があります。ここにリストされているものに加えて多くがあります。

- 編集 -

また、プログラムが何かを実行していることを確認するために、プログラムの開発中にいくつかのトレースを追加することをお勧めします。

例えば

bool knighttour(square pt,int &counter,int cb[][8]) {

printf("\r%d    ", counter);  // <<<---
Marksquare(cb[pt.x][pt.y],counter);
if (counter==64)
    return true;

counter++;

Vector <square> temp = generatemoves(pt);

for (int i=0;i<temp.size();i++)
{
    if (IsLegal(temp[i],cb))
        knighttour(temp[i],counter,cb);
}

Unmarksquare(cb[pt.x][pt.y]);
counter--;
return false;

}
于 2011-09-20T20:39:28.867 に答える
1

このコードは、おそらくナイツ ツアーで考えられるすべてのルートを見つけようとし、最後に見つかったルートを返します。

それ以外の

for (int i=0;i<temp.size();i++)
{
    if (IsLegal(temp[i],cb))
        knighttour(temp[i],counter,cb);
}

試す

for (int i=0;i<temp.size();i++)
{
    if (IsLegal(temp[i],cb))
    {
        if(knighttour(temp[i],counter,cb))
        { 
             return true;
        }
    }

}
于 2011-09-20T20:51:38.227 に答える
0

私が見ていることの1つは、knighttourにいるreturn trueときcounter==64は伝播されませんが、それを呼び出す関数はfalseを返すため、main（）で気付くことはありません。

とはいえ、アルゴリズムを修正しても、一生のうちに終了しない可能性があります。

于 2011-09-20T20:40:54.380 に答える