0

8*8 のチェス盤で Knight の巡回問題を解こうとしています。しかし、私のバックトラックは無限ループに陥っています。私のロジック機能は次のとおりです。

N は 8 です。

  boolean algo(int x,int y,int no_of_moves,int sol[][]){

        if(no_of_moves==N*N){
            return true;
        }

        int nextx;
        int nexty;
        for(int i=0;i<8;i++){

            nextx=x+move_x[i];
            nexty=y+move_y[i];

            if(is_valid(nextx,nexty)){
                sol[nextx][nexty]=no_of_moves;

                if(algo(nextx,nexty,no_of_moves+1,sol)){
                    return true;
                }
                else
                    sol[nextx][nexty]=-1;

            }
        }
        return false;  
    }

sol [][] は、騎士が行った動きを格納します。

配列 move_x と move_y は、騎士の次の位置を取得するために x と y に追加される値を格納します。

 int move_x[]={  2, 1, -1, -2, -2, -1,  1,  2 };
    int move_y[]={  1, 2,  2,  1, -1, -2, -2, -1 };

まず、x を 0、y を 0、no_of_moves を 1 として渡し、sol[0][0] 以外の sol[][] のすべての値を 0 として渡しました。

とがチェス盤の内側にあり、まだアクセスされていないis_valid()かどうかをチェックします。nextxnexty

boolean is_valid(int xnext,int ynext)
    {
        if(xnext>=0 && xnext<N && ynext>=0 && ynext<N && sol[xnext][ynext]==-1)
        { 
            return true;
        }
        else 
        {
            return false; 
        }
    }
4

2 に答える 2

0

そこで力ずくを使っているようですが、それではこの問題を妥当な時間内に解決するには不十分です。最適化がなければ、複雑になりますO(N^(N*N))(N はボードの次元です)。したがって、最初の解決策を見つけるには、本当に永遠の時間がかかる場合があります。それが無限ループにあると思った理由です。

最も効率的な最適化は、1823 年に初めて発表されたWarnsdorff の規則です。これは、最初の試行で (すぐに) 解を見つけることができる一種の単純なヒューリスティック規則です。

于 2022-01-23T02:17:04.777 に答える