java - 骑士之旅需要回溯

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 进行平衡清除那个方 block - 你没有这样做。

这不是您的代码的唯一问题，而是主要问题。

存在回溯的替代方法。您可以在任何递归级别创建一个新板，它是当前板的副本，但通常被认为是浪费内存。

这是我最终得到的代码:

// 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 数组静态 - 它们不需要是参数。
3. 在一个地方完成所有检查(机上和空的)。
4. 在有惊无险的情况下打印公告板，只是为了让您开心。
5. 使用 static final EMPTY 来表示空。
6. 完成后返回一个 boolean 结果以停止搜索。
7. 添加了回溯。
8. 使用更好的名称，例如 board 和 knightsMove。
9. 使用常量 SIZE 作为电路板尺寸。
10. 可能会进行一些小的调整。

请不要将此代码用于您的家庭作业 - 通过自己动手并了解每个部分的原因，您将学到更多。