java recurison - バックトラックを解決するためのヘルプが必要ナイトツアー

Question

私はナイトツアーの問題に取り組んでいます。 私のプログラムでは、ユーザーは3以上の数値nを選択できます。この数値は、テーブルのサイズを2次元配列でn * nだけ決定します。その後、騎士は0以上の値であれば、ユーザーから与えられた出発点に基づいてツアーを開始します。

騎士が死んでしまったときに問題が発生します。出力の視覚化テーブル）。 私は何とか動きを追跡して、行き止まりを阻止し、ステップを遡ってそこから試してみることができます。私は3次元の配列が必要なので、各四角形のすべてのターン番号を保存できるようになったとわかりました。しかし、再び私はArrayListの魔女が静的でない必要があります。どんな提案も感謝します。ここに私のコードは次のとおりです。4 * 4のテーブルの

package knightsTour; 

    import java.util.Scanner; 
    import java.util.ArrayList; 

    public class KnightsTour 
    { 
     private static int turns = 0; 
     private static ArrayList<String> moves = new ArrayList<String>(); 

     private static int squares; 
     private static int table[][]; 

     private static boolean takeTour(int x, int y) { 
      // Checks if all squares is used. If true, algorithm will stop 
      if (checkIfFinished()) 
       return true; 

      table[x][y] = ++turns; 

      // 2 Left, 1 Down 
      if (x > 1 && y < squares -1 && table[x-2][y+1] == 0) 
      { 
       moves.add("X: " + x + ", Y: " + y + ". Moving 2 Left, 1 Down. Turn: " + turns); 
       if (takeTour(x-2, y+1)) 
       { 
        return true; 
       } 
       else 
       { 
        return false; 
       } 
      } 
      // 2 Left, 1 Up 
      if (x > 1 && y > 0 && table[x-2][y-1] == 0) 
      { 
       moves.add("X: " + x + ", Y: " + y + ". Moving 2 Left, 1 Up. Turn: " + turns); 
       if (takeTour(x-2, y-1)) 
       { 
        return true; 
       } 
       else 
       { 
        return false; 
       } 
      } 
      // 2 Up, 1 Left 
      if (y > 1 && x > 0 && table[x-1][y-2] == 0) 
      { 
       moves.add("X: " + x + ", Y: " + y + ". Moving 2 Up, 1 Left. Turn: " + turns); 
       if (takeTour(x-1, y-2)) 
       { 
        return true; 
       } 
       else 
       { 
        return false; 
       } 
      } 
      // 2 Up, 1 Right 
      if (y > 1 && x < squares -1 && table[x+1][y-2] == 0) 
      { 
       moves.add("X: " + x + ", Y: " + y + ". Moving 2 Up, 1 Right. Turn: " + turns); 
       if (takeTour(x+1, y-2)) 
       { 
        return true; 
       } 
       else 
       { 
        return false; 
       } 
      } 
      // 2 Right, 1 Up 
      if (x < squares -2 && y > 0 && table[x+2][y-1] == 0) 
      { 
       moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Up. Turn: " + turns); 
       if (takeTour(x+2, y-1)) 
       { 
        return true; 
       } 
       else 
       { 
        return false; 
       } 
      } 
      // 2 Right, 1 Down 
      if (x < squares -2 && y < squares -1 && table[x+2][y+1] == 0) 
      { 
       moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Down. Turn: " + turns); 
       if (takeTour(x+2, y+1)) 
       { 
        return true; 
       } 
       else 
       { 
        return false; 
       } 
      } 
      // 2 Down, 1 Right 
      if (y < squares -2 && x < squares-1 && table[x+1][y+2] == 0) 
      { 
       moves.add("X: " + x + ", Y: " + y + ". Moving 2 Down, 1 Right. Turn: " + turns); 
       if (takeTour(x+1, y+2)) 
       { 
        return true; 
       } 
       else 
       { 
        return false; 
       } 
      } 
      // 2 Down, 1 Left 
      if (y < squares -2 && x > 0 && table[x-1][y+2] == 0) 
      { 
       moves.add("X: " + x + ", Y: " + y + ". Moving 2 Down, 1 Left. Turn: " + turns); 
       if (takeTour(x-1, y+2)) 
       { 
        return true; 
       } 
       else 
       { 
        return false; 
       } 
      } 
/* 
      I need some code here before it gives up searching 
*/ 
      // If we'd tried every single paths 
      // and we still end up here, there's no solution 
      return false; 
     } 

     // Checks if all squares is used 
     private static boolean checkIfFinished() 
     { 
      for (int i = 0; i < squares; i++) 
      { 
       for (int j = 0; j < squares; j++) 
       { 
        if (table[i][j] == 0) 
         return false; 
       } 
      } 
      return true; 
     } 

     // Made this to save code from 3 duplicates 
     private static void invalidNumber() 
     { 
      System.out.println("Invalid number! Killing proccess"); 
      System.exit(0); 
     } 

     public static void main(String[] args) { 

      Scanner sc = new Scanner(System.in); 
      System.out.print("Number of squares: "); 
      squares = Integer.parseInt(sc.nextLine()); 
      if (squares < 3) 
       invalidNumber(); 

      System.out.println("Note: Start values is from 0 -> n-1" 
          + "\n0,0 is at top left side"); 
      System.out.print("X start value: "); 
      int x = Integer.parseInt(sc.nextLine()); 
      if (x < 0 || x > squares -1) 
       invalidNumber(); 

      System.out.print("Y start value: "); 
      int y = Integer.parseInt(sc.nextLine()); 
      if (y < 0 || y > squares -1) 
       invalidNumber(); 
      sc.close(); 

      table = new int[squares][squares]; 

      boolean tourComplete = takeTour(x, y); 

      for (String s : moves) 
      { 
       System.out.println(s); 
      } 
      if (!tourComplete) 
       System.out.println("Did not find any way to complete Knights Tour!"); 

      // Print the table with the move-numbers 
      for (int i = 0; i < squares; i++) 
      { 
       for (int j = 0; j < squares; j++) 
       { 
        System.out.printf("%4d", table[j][i]); 
       } 
       System.out.println(); 
      } 
     } 
    } 

私の出力は次のようになります。

Number of squares: 4 
Note: Start values is from 0 -> n-1 
0,0 is at top left side 
X start value: 0 
Y start value: 0 
X: 0, Y: 0. Moving 2 Right, 1 Down. Turn: 1 
X: 2, Y: 1. Moving 2 Left, 1 Down. Turn: 2 
X: 0, Y: 2. Moving 2 Up, 1 Right. Turn: 3 
X: 1, Y: 0. Moving 2 Right, 1 Down. Turn: 4 
X: 3, Y: 1. Moving 2 Left, 1 Down. Turn: 5 
X: 1, Y: 2. Moving 2 Up, 1 Right. Turn: 6 
X: 2, Y: 0. Moving 2 Left, 1 Down. Turn: 7 
X: 0, Y: 1. Moving 2 Right, 1 Down. Turn: 8 
X: 2, Y: 2. Moving 2 Left, 1 Down. Turn: 9 
X: 0, Y: 3. Moving 2 Up, 1 Right. Turn: 10 
X: 1, Y: 1. Moving 2 Right, 1 Up. Turn: 11 
Did not find any way to complete Knights Tour! 
    1 4 7 12 
    8 11 2 5 
    3 6 9 0 
    10 0 0 0 

Answer 1

あなたはすべての再帰ステップでそれらすべてをチェックする必要があるバックトラックに異なる可能性をしようとします。あなたが1つのステップで提供するコードでは、1つの可能性を試してから戻ってくるだけです。これを行うと、すべての可能性を探ることができません。

私の提案は、現在の位置（x、y）を受け入れるように関数の引数を変更し、以前に訪れた位置のブール値の配列を変更することです。最終的な有効なソリューションのパスを構築する必要がある場合は、ステップ数（実行したステップ数）と、どのステップでどのポジションを訪問したかを格納するint配列を追加することをお勧めします。

次に、私は最も効率的ではない解決法を提供します。実際には、再帰の爆発（CPU効率）を避けるためにバックトラックの可能性を刈り取ってみることもできますし、行列のコピーをいくつか（メモリ効率）避けることもできます。

package knightsTour; 

import java.util.Scanner; 


public class KnightsTour { 

private static final int[] MOVE_X = new int[] { -2, -2, -1, -1, +1, +1, +2, +2 }; 
private static final int[] MOVE_Y = new int[] { +1, -1, +2, -2, +2, -2, +1, -1 }; 

private final int SQUARES; 
private final int INIT_X; 
private final int INIT_Y; 

private int[][] path; 


public KnightsTour(int squares, int x, int y) { 
    this.SQUARES = squares; 
    this.INIT_X = x; 
    this.INIT_Y = y; 
} 

public int[][] getPath() { 
    return this.path; 
} 

public boolean takeTour() { 
    boolean[][] visited = new boolean[this.SQUARES][this.SQUARES]; 
    for (int i = 0; i < this.SQUARES; ++i) { 
     for (int j = 0; j < this.SQUARES; ++j) { 
      visited[i][j] = false; 
     } 
    } 
    visited[this.INIT_X][this.INIT_Y] = true; 

    this.path = new int[this.SQUARES][this.SQUARES]; 

    return takeTourBT(this.INIT_X, this.INIT_Y, 0, visited, this.path); 
} 

private boolean takeTourBT(int posX, int posY, int step, boolean[][] visited, int[][] path) { 
    debug(step, visited); 

    if (checkIfFinished(visited)) { 
     return true; 
    } 

    // Increase the step count 
    ++step; 

    // Try recursively (cut when a branch success) 
    boolean success = false; 
    for (int i = 0; i < MOVE_X.length && !success; ++i) { 
     int nextX = posX + MOVE_X[i]; 
     int nextY = posY + MOVE_Y[i]; 
     if (nextX >= 0 && nextX < this.SQUARES && nextY >= 0 && nextY < this.SQUARES && !visited[nextX][nextY]) { 
      // Next position is valid and has not been visited 
      // Mark position 
      visited[nextX][nextY] = true; 
      // Call 
      boolean branchSuccess = takeTourBT(nextX, nextY, step, visited, path); 
      if (branchSuccess) { 
       // We are comming back from the good solution, mark the path 
       path[nextX][nextY] = step; 
      } 
      success = success | branchSuccess; 
      // Unmark the position for next try 
      visited[nextX][nextY] = false; 
     } 
    } 

    return success; 
} 

// Adds some verbose for debugging 
private void debug(int step, boolean[][] visited) { 
    System.out.println("*********************** STEP " + String.valueOf(step) + " ***********************"); 
    for (int i = 0; i < this.SQUARES; ++i) { 
     for (int j = 0; j < this.SQUARES; ++j) { 
      if (visited[i][j]) { 
       System.out.print("X "); 
      } else { 
       System.out.print(". "); 
      } 
     } 
     System.out.println(""); 
    } 
    System.out.println("*******************************************************"); 
} 

// Checks if all squares is used 
private boolean checkIfFinished(boolean[][] visited) { 
    for (int i = 0; i < this.SQUARES; ++i) { 
     for (int j = 0; j < this.SQUARES; ++j) { 
      if (!visited[i][j]) { 
       return false; 
      } 
     } 
    } 

    return true; 
} 

public static void main(String[] args) { 
    // Process arguments 
    int squares = 0; 
    int x = 0; 
    int y = 0; 
    try (Scanner sc = new Scanner(System.in)) { 
     System.out.print("Number of squares: "); 
     squares = Integer.parseInt(sc.nextLine()); 
     if (squares < 3) { 
      throw new Exception("[ERROR] Invalid number of squares"); 
     } 

     System.out.println("Note: Start values is from 0 -> n-1" + "\n0,0 is at top left side"); 
     System.out.print("X start value: "); 
     x = Integer.parseInt(sc.nextLine()); 
     if (x < 0 || x > squares - 1) { 
      throw new Exception("[ERROR] Invalid start x position"); 
     } 

     System.out.print("Y start value: "); 
     y = Integer.parseInt(sc.nextLine()); 
     if (y < 0 || y > squares - 1) { 
      throw new Exception("[ERROR] Invalid start y position"); 
     } 
    } catch (Exception e) { 
     // Error occurred, exit 
     System.err.println("Killing process"); 
     System.exit(1); 
    } 

    // Initialize the KnightsTour 
    KnightsTour kt = new KnightsTour(squares, x, y); 

    // Make the tour 
    boolean success = kt.takeTour(); 

    // Post process 
    if (success) { 
     System.out.println("The tour was sucessfull!"); 
    } else { 
     System.out.println("Did not find any way to complete Knights Tour!"); 
    } 

    int[][] path = kt.getPath(); 
    for (int i = 0; i < path.length; ++i) { 
     for (int j = 0; j < path[i].length; ++j) { 
      String stepSTR = (path[i][j] < 10) ? "0" + String.valueOf(path[i][j]) : String.valueOf(path[i][j]); 
      System.out.print(stepSTR + " "); 
     } 
     System.out.println(""); 
    } 
} 

} 

このコードをサイズ5で開始位置（0,0）にしてください。

ていることに注意してください：

あなたが有効/私はあなたが複製を避けるために2つのアレイと移動を行う方法を固めデバッグコール
• をコメントではなく、明確化のために、デバッグの繰り返しを無効にすることができ
• ます再びそれを展開することができます。
• 各再帰ステップで、深さに入る前に、移動を実行できるかどうかを確認し、次の位置をマークして処理を進めます。途中でポジションのマークを外し、移動が成功したかどうかを確認し、必要に応じて良い解決策を再構築します。