0

我是编程新手，想解决 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 从那个点到 0,3。它不应该那样做，我试图弄清楚但我做不到。任何人都可以帮我解决这个问题，并告诉我这是如何发生的以及为什么会发生。

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

谢谢。

4

2 回答 2

2

您在这里有几个问题：

  1. 你的程序只有一个访问过的方块的表示，当你遇到死胡同和回溯时，你永远不会重置它们。
  2. 无论您后来是否发现路径是死胡同并且您需要退出，您都会输出每个访问过的方块。
  3. 您无法确定自己何时真正成功地完成了一次旅行。您的程序停止的唯一原因是某些失败的旅行组合将每个广场标记为已访问，然后您的程序在无法进一步移动时结束。

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

于 2013-04-28T19:18:44.720 回答
1

仅仅因为您打印出 0,0 然后 3,1 并不意味着直接从0,0 访问了 3,1。您所知道的是，在0,0之后的某个时间访问了 3,1。

这是您的程序的修改版本，它通过打印出每个正方形从哪个正方形访问来演示这一点：

public class Knight_tour{

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


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


    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 + " (visited from " + fromX + ", " + fromY + ")");

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

        }
}        

}        

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

    }
}

输出：

0 1 (visited from 0, 1)
2 2 (visited from 0, 1)
3 0 (visited from 2, 2)
1 1 (visited from 3, 0)
3 2 (visited from 1, 1)
1 3 (visited from 3, 2)
2 1 (visited from 1, 3)
3 3 (visited from 2, 1)
1 2 (visited from 3, 3)
2 0 (visited from 1, 2)
0 0 (visited from 1, 2)
3 1 (visited from 1, 2)
2 3 (visited from 3, 1)
0 2 (visited from 2, 3)
1 0 (visited from 0, 2)
0 3 (visited from 1, 1)
于 2013-04-28T19:32:20.100 回答