java - 基本骑士之旅算法

Question

我是编程新手，想解决 Knights Tour 问题作为练习。所以我试了一下。我刚刚学习了递归的概念，并尝试用它来解决 4X4 板的这个问题。我的代码是:

public class Knight_tour{

private static boolean[][] chessboard = new boolean[4][4];


public static void Knight_tour(int x,int y) {


    if(((x < 0) || (x >= 4) || (y <0) || (y >= 4))){
       //do nothing
    }else{
        if(chessboard[x][y] == true){

           //if it is already visited, then, do nothing.
        }
        if(chessboard[x][y] != true) {
           //If it is not visited then find more points like this.
         chessboard[x][y]=true;
         System.out.println(x +" "+ y);

         Knight_tour(x+2, y+1);
         Knight_tour(x+1, y-2);
         Knight_tour(x+1, y+2);
         Knight_tour(x-1, y+2);
         Knight_tour(x-2, y-1);
         Knight_tour(x-2, y+1);
         Knight_tour(x-1, y-2);
         Knight_tour(x+2, y-1);  

        }
}        

}        

public static void main(String[] args){
           Knight_tour(0, 1);

    }
}

现在，当我运行它时，我得到以下输出:

0 1

2 2

3 0

1 1

3 2

1 3

2 1

3 3

1 2

2 0

0 0

3 1

2 3

0 2

1 0

0 3

这给了我按访问顺序排列的盒子在板上的位置。我的问题是:

1. 点 0,0 到 3,1，倒数第二个点是 1,0，它从 1,0 到 0,3。它不应该这样做，我试图弄清楚这一点，但我做不到。谁能帮我解决这个问题，并告诉我这是如何以及为什么会发生。

2. 这也能解决吗？我的意思是，我确信有许多复杂和更复杂的算法，但我只是想要一些练习递归的东西。我学习了 DFS 算法，有点感觉，这需要同样的东西。如果不能，可以任何人都指出我正确的方向(一个简单的方法来实现这个工作，它不需要它针对速度或任何东西进行优化)。

谢谢。

Answer 1

您遇到了一些问题:

1. 您的程序对所访问的方 block 有一个单一的表示，当您遇到死胡同并原路返回时，您永远不会重置它们。
2. 您可以边走边输出每个访问过的方格，无论您后来是否发现该路径是一条死胡同并且需要退出。
3. 您无法确定自己何时真正成功完成了一次游览。你的程序停止的唯一原因是失败的旅行的某种组合将每个方 block 标记为已访问，然后当无法进一步移动时你的程序结束。

您需要去思考您的算法，也许还需要阅读其他人的解决方案。