在骑士之旅中需要回溯

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;