骑士之旅需要回溯

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

在骑士巡回赛问题中需要回溯是至关重要的。您没有在代码中实现回溯是它不起作用的主要原因。

要修复它，您至少必须清除方法末尾的位置。也就是说，当您执行 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

我做了以下修改：

添加了注释 - 您应该始终对您的代码进行注释。
创建 x 和 y 数组 static - 它们不需要作为参数。
将所有支票（机上和空的）放在一个地方。
在有惊无险的情况下打印公告板，只是为了让您开心。
用了一个static final EMPTY来表示空。
Return 完成后会出现 boolean 结果以停止搜索。
添加回溯。
使用更好的名称，例如 board 和 knightsMove。
电路板尺寸使用常量 SIZE。
可能有一些小的调整。

请不要将此代码用于您的家庭作业 - 通过自己执行此代码并理解为什么每个部分都有效，您将学到更多。

Answer 2

递归是 function/method 调用自身。您的 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;

骑士之旅需要回溯

Need of backtracking in Knight’s tour

java

algorithm

backtracking

knights-tour