遞歸Java編程，騎士旅行我發瘋

Question

我一直在一所學校的項目，不能找出問題。當死亡發生時，騎士跳回到最後一步的問題。

我已經爲4x4測試添加了輸出，並且您可以清楚地看到騎士在看到從第12號開始有死路時跳回到第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(); 
      } 
     } 
    } 

下面是一個4x4的輸出：

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（x + -a，y + -b））語句在takeTour（int x，int y）內部，則必須在每8個字節中放入其他塊，然後返回false。現在我只是想知道如何跟蹤圖案，以便我可以返回一步並嘗試新的圖案

Answer 2

你最好的選擇將是一個List<Point> visited添加到您的遞歸調用方法。我還會將您的int x和int y參數更改爲Point。通過這種方法，您可以直接致電visited.contains(point)來確定您是否已經完成了對該Point的測試。在這種情況下，您不會使用該特定的Point進行遞歸調用，然後轉到下一個。