1

我正在尝试使用 java 中的回溯和递归来解决 4x4 板上的骑士之旅问题，并且在输出中我得到以下步骤序列：

1 13 16 15
10 7 4 14
5 2 11 8
12 9 6 3

在右上角，14、15和16相邻，这是不可能的，因为骑士在棋盘上移动成L形。如果有人可以帮助我解决这个问题，我将不胜感激。

编码：

public class KnightsTour {

private static int board[][] = new int[4][4];
private static int stepCounter = 1;

public Test() {
    initBoard(board);
    tour(0,0);
    printSol(board);

}

  public static void printSol(int[][] a) {
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a[i].length; j++) {
            if(a[i][j]>9){
                System.out.print(a[i][j] + "  ");
            }else{
                System.out.print(a[i][j] + "   ");
            }
        }
        System.out.println();
    }
    System.out.println();
}


public static void initBoard(int[][] a) {
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a[i].length; j++) {
            a[i][j] = -1;
        }
    }
}


public void tour(int x, int y) {


    if (((x < 0) || (x >= 4) || (y < 0) || (y >= 4)) || (board[x][y] != -1)) {
        return;
    }else{
        board[x][y] = stepCounter++;
        tour(x+2, y+1);
        tour(x+1, y-2);
        tour(x+1, y+2);
        tour(x-1, y+2);
        tour(x-2, y-1);
        tour(x-2, y+1);
        tour(x-1, y-2);
        tour(x+2, y-1);  
    }
}




public static void main(String[] args){
    new KnightsTour();
}
}
4

2 回答 2

1

  • 您需要使函数返回一个布尔值，以便它可以告诉调用函数它是否成功。否则，即使在找到解决方案之后，您也只能继续尝试所有可能的组合。

    然后，在每次调用函数时，都需要检查返回值，如果成功则返回 true。

    然后你显然还需要在完成后返回 true。

    我建议类似：

    if (stepCounter == 1 + board.length * board[0].length)
  return true;

    紧随其后board[x][y] = stepCounter++;。

  • 您需要还原在函数调用结束时所做的任何更改，即stepCounter需要减少并board[x][y]需要设置为-1.

成功完成这些更改后，您应该会看到 all -1's 的结果，因为这在 4x4 板上是不可能的，但将其更改为 8x8 应该会成功。

请注意，我没有在17上面使用 - 最好不要使用硬编码值（例如，在 中x >= 4）。请改用数组的大小或final值。

于 2013-12-23T20:26:08.087 回答
0

您的 tour() 函数似乎将正方形的值设置为第一次访问的订单的计步器。但是您正在尝试多种选择。当您到达 12 时，您的第一次巡回赛死路一条 - 随后的一次尝试触及 13-16 格中的每一个。

您需要存储当前游览的状态，而不是您访问的顺序。例如，如果您回溯，则当前广场不再是游览的一部分。如果你找到了一个旅行，你应该停下来，因为你已经完成了。

于 2013-12-23T20:22:35.007 回答