ナイトツアー再帰で解決策が見つかりません

Question

ナイトツアーは以前に依頼されましたが、まだ問題があります。私はチェス盤のすべての細胞を訪問する再帰を試みていますが、私は52回以上訪問することはできません。その後、バックトラックし、訪問したセルの数がカウントダウンします。

public class Ch7E22_3 { 
    public static int[][] chess; 
    public static int[][] adjacent; 

    public static void main(String[] args) { 
     chess = new int[8][8]; 
     adjacent = new int[][] { { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 }, { -1, 2 }, { 1, -2 }, 
       { -1, -2 } }; 
     initializeChess(); 
     move(1, 0, 0); 
    } 

    private static void move(int cnt, int row, int col) { 
     chess[row][col] = cnt; 
     if (cnt == (8 * 8)) { 
      System.out.println("You moved around all cells: " + cnt); 
     } else { 
      for (int i = 0; i < 8; i++) { 
       if (((row + adjacent[i][0] >= 0) && (row + adjacent[i][0]) < 8) 
         && ((col + adjacent[i][1] >= 0) && (col + adjacent[i][1] < 8))) { 
        if (chess[row + adjacent[i][0]][col + adjacent[i][1]] == 0) { 
         row = row + adjacent[i][0]; 
         col = col + adjacent[i][1]; 
         cnt++; 
         System.out.println(row + " " + col + " cnt = " + cnt); 
         move(cnt, row, col); 
        } 
       } 
      } 
     } 
     chess[row][col] = 0; 
    } 

    private static void initializeChess() { 
     for (int i = 0; i < 8; i++) { 
      for (int j = 0; j < 8; j++) { 
       chess[i][j] = 0; 
      } 
     } 
    } 
} 

Answer 1

最初の問題はここにある：

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

だから、あなたはループのためにそれを行う必要がありここに私のコードです。まず、あなたの再帰呼び出しを行い、そしておそらくヒットした場合、右あなたの最初の各時間：あなたは51

でCNTを入力して頂きます今、あなたは

if (... some overly complicated condition ...) { 
    ... cnt++ 
    move(cnt, 

は何今起こっています。したがって、あなたはcntを増やして再帰します。したがって、印刷物にはcntがどのように増加しているかが示されます。

しかし、ある時点で、再帰はで終了します。if条件はこれ以上真ではありません。したがって、再帰的に呼ばれるメソッド...が終了します。しかし、覚えておいてください：あなたはそのメソッドを呼び出しました... への別の呼び出しからへの呼び出し。そして、それはまだループしているかもしれません。さらに重要なのは、です。 move（）は、自身のバージョンのcntを持っています。

ローカル変数があなたのボードに似た変数になるように、変数cntを変更してください！あなたはそれを行うときに、あなたはあなたのコードが実際に印刷していることがわかります：

... 
3 7 cnt = 52 
2 4 cnt = 53 
... 
2 3 cnt = 64 
You moved around all cells: 64 
0 4 cnt = 65 
... 

を実際に

4 0 cnt = 126 

意味で、後に停止するには：CNTの印刷は自分のアルゴリズムの副作用が実際に動作していません正しく！

最後に：私は解散することをお勧めしますあなたの

private static isXyz(...) 

などの小さなヘルパーメソッドのセットに条件が、その内のこれらのメソッドを呼び出すことがあれば、if文 - それは読みやすさを大幅に役立つだろう！

Answer 2

バックトラックが正しくありません。最後の行が実行されるまでに、chess[row][col]を0に戻すと、rowとcolがほぼ確実に変更されました。

メソッド内でrow,col、cntを変更しないでください。再帰呼び出しに新しい値を渡すだけです。このような何か、私はあなたのロジックの残りの部分をチェックしていないしていないにもかかわらず：あなたが唯一のその後の再帰呼び出しに渡された値を修正することで一貫していることを確認するには

for (int i = 0; i < 8; i++) { 
     int nextrow = row + adjacent[i][0]; 
     int nextcol = col + adjacent[i][1]; 
     if (nextrow >= 0 && nextrow < 8 && 
       nextcol >= 0 && nextcol < 8) { 
      if (chess[nextrow][nextcol] == 0) { 
       System.out.println(nextrow + " " + nextcol + " cnt = " + (cnt+1)); 
       move(cnt+1, nextrow, nextcol); 
      } 
     } 
    } 

、そして決して内でそれらを変更しますメソッドを使用すると、パラメータをfinalにすることができます。

private static void move(final int cnt, final int row, final int col) { 
    ... 
}