我是编程新手,想解决 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
这使我按照访问顺序在板上的框位置。我的问题是:
点 0,0 到 3,1,倒数第二个点是 1,0 从那个点到 0,3。它不应该那样做,我试图弄清楚但我做不到。任何人都可以帮我解决这个问题,并告诉我这是如何发生的以及为什么会发生。
这甚至可以像这样解决吗?我的意思是我确信有许多复杂和更复杂的算法,但我只是想要一些东西来练习递归。我学习了 DFS 算法,有点感觉,这需要同样的东西。万一它不能,可以任何人都指出我正确的方向(一个简单的方法来让它工作,它不需要针对速度或任何东西进行优化)。
谢谢。