Knight 的巡回递归方法 Java

Question

我正在尝试递归地实现骑士之旅.. 下面是我的代码。为了简单起见，我选择了 5x5 的板。我的目标是打印出正确的骑士位置，并可能与打印语句同时显示回溯。

class Knight
{
public boolean[][] board = new boolean[5][5];

public final int SQUARES = 5*5-1;

public Knight()
{

    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            board[i][j] = false;

}

public boolean tour(int x, int y, int visitedX, int visitedY,int n)// x,y coords, just visited x,y and counter n
{

    if(x>=5||y>=5||x<0||y<0){ //out of bounds
        System.out.println("Visited "+x+", "+y+" Out of bounds");
        System.out.println("Back to "+visitedX+", "+visitedY);
        return false;
    }
    else{
        if(board[x][y] == true)
        {return false;}
        if(board[x][y]!=true){
            boolean result = false;
            board[x][y]=true;
            System.out.println("Visited "+x+", "+y);
            result = tour(x+2,y+1,x,y,n+1); 
            result = tour(x+2,y-1,x,y,n+1); 
            result = tour(x+1,y-2,x,y,n+1); 
            result = tour(x-1,y-2,x,y,n+1); 
            result = tour(x+1,y+2,x,y,n+1); 
            result = tour(x-1,y+2,x,y,n+1);
            result = tour(x-2,y-1,x,y,n+1); 
            result = tour(x-2,y+1,x,y,n+1); 

        }
    }
    return false;
}
}
public class KnightTApp {

public static void main(String[] args) {
    Knight k = new Knight();
    k.tour(0,0,0,0,0);

}

}

部分打印输出

Visited 4, 0
Visited 6, 1 Out of bounds
Back to 4, 0
Visited 6, -1 Out of bounds
Back to 4, 0
Visited 5, -2 Out of bounds
Back to 4, 0
Visited 3, -2 Out of bounds
Back to 4, 0
Visited 5, 2 Out of bounds
Back to 4, 0
Visited 2, -1 Out of bounds
Back to 4, 0
Visited 2, 0

我的问题是在过程的中间，我运行在索引 4,0 处陷入死胡同（不是所有的方块都被覆盖，但我无法采取合法的行动）。而且由于我没有包含任何 backtracking 的行。它只是跳到索引 2,0，这甚至不是合法的骑士移动。

我的问题是如何用 if 语句表达死胡同的情况[=27=]？我想我应该将递归设置为某种布尔值并从那里开始，但我不知道该怎么做。

而且使用递归和使用DFS（深度优先搜索）也是一样的，因为它们基本上有相同的想法？

提前谢谢你。

Answer 1

您可能想要使用 Stack 数据结构，并在每次移动时评估所有可能的有效移动，将每个移动推入堆栈。当您进行有效移动时，将其从堆栈中弹出。

死胡同的情况是当你的评估方法 returns 0 可能的移动。

Answer 2

您需要弄清楚您是否正在尝试识别所有可能的游览或者只是为了找到一个有效的旅游。

要获得完整的回溯，您需要在游览结束时 return 向调用者发送消息时再次将棋盘字段标记为空闲。

其次，您需要检查 tour() 上每个递归调用的结果。如果为 true，则您找到了一个有效的星座，您也可以 return 返回 true。否则尝试下一个可能的移动。如果没有向左移动 return false.

最后你错过了一个合适的终止条件："What is success?" 在您的情况下，如果您有 5x5 个成功的移动，所有字段都已访问，您可能只是 return true 表示成功。

您可能还想跟踪移动顺序，以便有机会输出一次成功的游览。

以上是针对识别一次成功的游览。
通过跟踪移动顺序，您可以跟踪所有成功的旅行，而不仅仅是 return 在最深的递归检查已知旅行时 return 为真，如果它是新旅行则 return 为真。

作为参考，您的代码的修改版本解决了 "find any" 部分：

class Knight {
    public final static int SIZE = 5;

    public boolean[][] board = new boolean[SIZE][SIZE];
    public String[] moves = new String[SIZE * SIZE];

    public Knight() {

        for (int i = 0; i < 5; i++ ) {
            for (int j = 0; j < 5; j++ ) {
                board[i][j] = false;
            }
        }

    }

    public boolean tour(final int x, final int y, final int n)
    {
        if (n >= SIZE * SIZE) {
            return true;
        } else if (x >= 5 || y >= 5 || x < 0 || y < 0) { // out of bounds
            return false;
        } else if (board[x][y]) {
            return false;
        } else {
            // System.out.println("Checking " + n + ": " + x + "," + y);
            board[x][y] = true;
            moves[n] = x + "-" + y;
            if (tour(x + 2, y + 1, n + 1)) {
                return true;
            }
            if (tour(x + 2, y - 1, n + 1)) {
                return true;
            }
            if (tour(x + 1, y - 2, n + 1)) {
                return true;
            }
            if (tour(x - 1, y - 2, n + 1)) {
                return true;
            }
            if (tour(x + 1, y + 2, n + 1)) {
                return true;
            }
            if (tour(x - 1, y + 2, n + 1)) {
                return true;
            }
            if (tour(x - 2, y - 1, n + 1)) {
                return true;
            }
            if (tour(x - 2, y + 1, n + 1)) {
                return true;
            }
            board[x][y] = false;
            moves[n] = null;
            return false;
        }
    }

    public static void main(final String[] args) {
        final Knight k = new Knight();

        for (int i = 0; i < SIZE; i++ ) {
            System.out.println("Starting at " + i + " 0");

            if (k.tour(i, 0, 0)) {
                k.printTour(true);
                break;
            }
            k.printTour(true);
        }
    }

    /**
     * @param result
     */
    private void printTour(final boolean result) {
        System.out.println("Found tour: " + result);
        int i = 0;
        if (result) {
            for (final String m : moves) {
                System.out.println("M-" + i + ": " + moves[i]);
                i++ ;
            }
        }
    }
}

Knight 的巡回递归方法 Java

Knight's tour recursive approach Java

java

recursion

knights-tour