在騎士之旅中需要回溯

Question

爲什麼我們需要回溯騎士之旅？ 我們可以通過只使用遞歸嗎？ 我試圖做到這一點，但它給出了錯誤的答案，我無法弄清楚代碼或邏輯出錯的地方。

import java.util.*; 
public class Solution { 

    public static void main(String[] args) { 
     Scanner s=new Scanner(System.in); 
     int[][] ans=new int[8][8]; 
     for(int d=0;d<8;d++){ 
      for(int e=0;e<8;e++){ 
       ans[d][e]=-1; 
      } 
     } 
     int[] x={2,1,-2,1,-1,-2,-1,2}; 
     int[] y={1,2,1,-2,-2,-1,2,-1}; 
     func(x,y,ans,7,7,1); 
    } 

    public static void func(int[] x,int[] y,int[][] ans,int i,int j,int count){ 
     if(count==64){ 
      for(int d=0;d<8;d++){ 
       for(int e=0;e<8;e++){ 
        System.out.print(ans[d][e]+" "); 
       } 
       System.out.println(); 
      } 
     } 
     if(ans[i][j]!=-1){ 
      return; 
     } 
     else{ 
      ans[i][j]=count; 
      for(int u=0;u<8;u++){ 
       if(i+x[u]>=0 && i+x[u]< 8 && j+y[u]>=0 && j+y[u]<8){ 
        func(x,y,ans,i+x[u],j+y[u],count+1); 
       } 
      } 
     } 
     return; 
    } 
} 

Answer 1

在騎士巡迴賽中需要追蹤追蹤問題至關重要。你沒有在你的代碼中實現你的回溯的事實是它不起作用的主要原因。

要修復它，您必須至少清除方法末尾的位置。 I.e當你做ans[i][j] = count你必須餘額，與ans[i][j] = -1清除該廣場 - 你不這樣做。

這不是你的代碼唯一的問題，但它是主要的問題。

存在備用追蹤的替代方案。您可以在遞歸級別上創建一個新的電路板，這是當前電路板的副本，但通常被認爲是浪費內存。

這是我結束了與代碼：

// The board size. 
private static final int SIZE = 8; 
// Contents of board squares when empty. 
private static final int EMPTY = -1; 
// The 8 possible x,y moves for the knight. 
private static final int[] x = {2, 1, -2, 1, -1, -2, -1, 2}; 
private static final int[] y = {1, 2, 1, -2, -2, -1, 2, -1}; 

public static void printBoard(int[][] board) { 
    // Print out the board. 
    for (int d = 0; d < SIZE; d++) { 
     for (int e = 0; e < SIZE; e++) { 
      System.out.print(board[d][e] + " "); 
     } 
     System.out.println(); 
    } 

} 

public static boolean knightsMove(int[][] board, int i, int j, int count) { 
    boolean finished = false; 
    // Only step onto empty squares that are on the board. 
    if (i >= 0 && i < SIZE && j >= 0 && j < SIZE && board[i][j] == EMPTY) { 
     // Mark my route. 
     board[i][j] = count; 
     // Count up. 
     count += 1; 
     // Are we done? 
     if (count > SIZE * SIZE) { 
      System.out.println("=== Solution ==="); 
      // Print the solution. 
      printBoard(board); 
      // Finished now. 
      return true; 
     } 
     if (count == SIZE * SIZE) { 
      // Nearly there - print something to show progress. 
      System.out.println("=== Try === (" + i + "," + j + ")=" + count); 
      // Print the current state. 
      printBoard(board); 
     } 
     // Look around to try all moves from here. 
     for (int u = 0; u < x.length && !finished; u++) { 
      // Try the next place. 
      finished = knightsMove(board, i + x[u], j + y[u], count); 
     } 
     // Clear my trail - you missed this. 
     board[i][j] = EMPTY; 
    } else { 
     // Cannot go there. 
     return false; 
    } 
    return finished; 
} 

public static void knightsMove() { 
    int[][] board = new int[SIZE][SIZE]; 
    // Clear to EMPTY. 
    for (int d = 0; d < board.length; d++) { 
     for (int e = 0; e < board[d].length; e++) { 
      board[d][e] = EMPTY; 
     } 
    } 
    // Start at (7,7) with count 1. 
    knightsMove(board, 7, 7, 1); 
} 

要有耐心 - 它需要很長的時間來完成 - 如你所願。在我的電腦需要大約20分鐘才能到：

=== Solution === 
29 42 51 60 27 22 17 24 
50 59 28 41 52 25 20 15 
43 30 61 26 21 16 23 18 
62 49 58 53 40 19 14 7 
57 44 31 48 33 8 3 10 
36 63 34 39 54 11 6 13 
45 56 37 32 47 2 9 4 
64 35 46 55 38 5 12 1 

我做了以下修改：

1. 添加的註釋 - 你應該總是註釋你的代碼。
2. 使您的x和y陣列static - 它們不需要是參數。
3. 在一個地方做了所有的檢查（船上和空）。
4. 打印幾乎未命中的紙板，只是爲了讓你流連忘返。
5. 使用static finalEMPTY表示空。
6. 返回一個boolean結果完成停止搜索那裏。
7. 追加回溯。
8. 使用更好的名稱，如board和knightsMove。
9. 用於板面尺寸的常量SIZE。
10. 可能是一些小的調整。

，請不要使用此代碼爲您的家庭作業 - 你將學會做這個自己，瞭解爲什麼每個部分的作品多。

Answer 2

遞歸是函數/方法調用自身的時候。您的func方法調用自己，因此您的程序使用遞歸。 （順便說一下：標識符應該是信息性的。調用函數function什麼都不說; tour會更好）。

回溯是當您通過嘗試一個分支接着另一個分支來探索分支問題，並且只有在完成當前分支後才檢查下一個分支。你的程序會這樣做，因此它正在使用回溯。

回溯，也可以用棧和循環來實現，就像這樣：

State initialState = new State(); // empty board, no moves 
Stack<State> stack = new Stack<State>(); 
stack.add(initialState); 
while (! stack.isEmpty()) { 
     State current = stack.pop(); 
     for (State next : current.getSuccesorStates()) { 
      if (next.isLegal()) { 
       stack.add(next); 
      } 
     } 
} 

這不使用遞歸。但是，通過遞歸（使用程序堆棧）執行此操作比較頻繁，如在代碼中一樣。

所以：你的問題需要回溯來解決它。它不需要遞歸，儘管你正在使用它。

額外信貸：您的代碼失敗，因爲您應該在完成訪問時取消標記單元格。這樣，當你嘗試下一個分支（它不會跳到那裏）時，單元格可以自由跳轉。請參閱//MISSING註釋。

if(ans[i][j]!=-1){ 
     return; 
    } 
    else{ 
     ans[i][j]=count; 
     for(int u=0;u<8;u++){ 
      if(i+x[u]>=0 && i+x[u]< 8 && j+y[u]>=0 && j+y[u]<8){ 
       func(x,y,ans,i+x[u],j+y[u],count+1); 
      } 
     } 
    } 
    // MISSING: un-mark last marking, so that other branches can be explored 
    ans[i][j]=-1 
    return;