0

私はプログラミングが初めてで、ナイツツアーの問題を練習として解決したいと考えていました。だから私はそれを試してみました。再帰の概念を学んだばかりで、それを使用して 4X4 ボードの問題を解決しようとしていました。私のコードは次のとおりです。 

public class Knight_tour{

private static boolean[][] chessboard = new boolean[4][4];


public static void Knight_tour(int x,int y) {


    if(((x < 0) || (x >= 4) || (y <0) || (y >= 4))){
       //do nothing
    }else{
        if(chessboard[x][y] == true){

           //if it is already visited, then, do nothing.
        }
        if(chessboard[x][y] != true) {
           //If it is not visited then find more points like this.
         chessboard[x][y]=true;
         System.out.println(x +" "+ y);

         Knight_tour(x+2, y+1);
         Knight_tour(x+1, y-2);
         Knight_tour(x+1, y+2);
         Knight_tour(x-1, y+2);
         Knight_tour(x-2, y-1);
         Knight_tour(x-2, y+1);
         Knight_tour(x-1, y-2);
         Knight_tour(x+2, y-1);  

        }
}        

}        

public static void main(String[] args){
           Knight_tour(0, 1);

    }
}

これを実行すると、次の出力が得られます。

0 1

2 2

3 0

1 1

3 2

1 3

2 1

3 3

1 2

2 0

0 0

3 1

2 3

0 2

1 0

0 3

これにより、ボード上のボックスの位置が、アクセスされた順序でわかります。私の質問は次のとおりです。

  1. ポイント 0,0 は 3,1 になり、最後から 2 番目のポイントは 1,0 になり、そこから 0,3 になります。それを行うべきではありません。これを理解しようとしましたが、できませんでした。誰でもこれで私を助けて、これがどのように、そしてなぜ起こっているのか教えてください。

  2. これもこのように解決できますか？つまり、 には複雑で複雑なアルゴリズムがたくさんあると確信していますが、再帰を練習する何かが欲しかっただけです。DFS アルゴリズムを学びましたが、これには同じことが必要だと感じました。誰でも私を正しい方向に向けてくれます(これを機能させるための簡単な方法です。速度などのために最適化する必要はありません)。

ありがとう。

4

2 に答える 2

2

ここにいくつかの問題があります。

  1. あなたのプログラムは、訪れた四角形の表現を 1 つ持っており、行き止まりにぶつかってバックトラックしたときに、これらをリセットすることはありません。
  2. パスが行き止まりであり、バックアウトする必要があるかどうかに関係なく、訪問したすべての正方形を出力します。
  3. 実際にツアーを無事に完了したかどうかはわかりません。プログラムが停止する唯一の理由は、失敗したツアーのいくつかの組み合わせがすべての正方形を訪問済みとしてマークし、それ以上の移動が不可能になったときにプログラムが終了することです。

自分のアルゴリズムについて考えてみる必要があり、おそらく他の人の解決策を読む必要があります。

于 2013-04-28T19:18:44.720 に答える