再帰的なJavaプログラミング、ナイトのツアーはナッツを動かす

Question

私は学校のプロジェクトに取り組んできましたが、問題を理解することはできません。最後のステップで致命的な終わりが起きたときに騎士がどこに戻ったかという問題。

4x4テスト用の出力を追加しました.Number12からのデッドウェイがあるとわかると、ナイトが11番にジャンプしていることがはっきりとわかります。その後、11番から "ツアーを解決する "。

また、パターンが問題を解決しない場合、私はどのように続行するのか不明です。それで、私は何とかそのパターンを記録して、私が同じパターンで何度も繰り返さないようにする必要があるからです。私の悪いEnglighと申し訳ありません申し訳ありません。ここで

 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"); 
       if (takeTour(x-2, y+1)) 
       { 
        return true; 
       } 
      } 
      // 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"); 
       if (takeTour(x-2, y-1)) 
       { 
        return true; 
       } 
      } 
      // 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"); 
       if (takeTour(x-1, y-2)) 
       { 
        return true; 
       } 
      } 
      // 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"); 
       if (takeTour(x+1, y-2)) 
       { 
        return true; 
       } 
      } 
      // 2 Right, 1 Up 
      if (x < squares -2 && y > 0 && table[x+2][y-1] == 0) 
      { 
       System.out.println("x:" + x + ", y:" + y + " (2r,1u)moving to x:" + (x+2) + ", y:" + (y-1)); 
       moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Up"); 
       if (takeTour(x+2, y-1)) 
       { 
        return true; 
       } 
      } 
      // 2 Right, 1 Down 
      if (x < squares -2 && y < squares -1 && table[x+2][y+1] == 0) 
      { 
       System.out.println("x:" + x + ", y:" + y + " (2r,1d)moving to x:" + (x+2) + ", y:" + (y+1)); 
       moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Down"); 
       if (takeTour(x+2, y+1)) 
       { 
        return true; 
       } 
      } 
      // 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"); 
       if (takeTour(x+1, y+2)) 
       { 
        return true; 
       } 
      } 
      // 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"); 
       if (takeTour(x-1, y+2)) 
       { 
        return true; 
       } 
      } 
      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 < 1) 
       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(); 
      } 
     } 
    } 

は、4×4用の出力です：

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 (2r,1d)moving to x:2, y:1 
x:1, y:0 (2r,1d)moving to x:3, y:1 
x:0, y:1 (2r,1d)moving to x:2, y:2 
x:1, y:1 (2r,1u)moving to x:3, y:0 
x:1, y:1 (2r,1d)moving to x:3, y:2 
x:1, y:2 (2r,1d)moving to x:3, y:3 
X: 0, Y: 0. Moving 2 Right, 1 Down 
X: 2, Y: 1. Moving 2 Left, 1 Down 
X: 0, Y: 2. Moving 2 Up, 1 Right 
X: 1, Y: 0. Moving 2 Right, 1 Down 
X: 3, Y: 1. Moving 2 Left, 1 Down 
X: 1, Y: 2. Moving 2 Up, 1 Right 
X: 2, Y: 0. Moving 2 Left, 1 Down 
X: 0, Y: 1. Moving 2 Right, 1 Down 
X: 2, Y: 2. Moving 2 Left, 1 Down 
X: 0, Y: 3. Moving 2 Up, 1 Right 
X: 1, Y: 1. Moving 2 Right, 1 Up 
X: 1, Y: 1. Moving 2 Right, 1 Down 
X: 3, Y: 2. Moving 2 Left, 1 Down 
X: 1, Y: 1. Moving 2 Down, 1 Right 
X: 1, Y: 2. Moving 2 Right, 1 Down 
Did not find any way to complete Knights Tour! 
    1 4 7 12 
    8 11 2 5 
    3 6 9 13 
    10 14 15 16 

Answer 1

問題を見つけました。 takeTour（int x、int y）の中にif（takeTour（x + -a、y + -b））のステートメントを入れてからfalseを返す必要がありました。今私はちょうど私が1つのステップを戻って新しいものを試すことができるようにパターンを追跡することができるだろうと思っています

Answer 2

あなたの最善の策は、あなたの再帰的に呼び出されるメソッドにList<Point> visitedを追加することです。 int xとint yのパラメータをPointに変更します。このようにしてvisited.contains(point)に電話して、すでにPointのテストを済ませているかどうかを判断できます。その場合は、その特定のPointを使用して再帰呼び出しを作成せず、次のものに移動します。