DFS算法-8-难题或nXn-游戏

Question

我想解决一个DFS算法。它是关于游戏8-puzzles或N x N拼图。在开始时，我有两个类似的数组( Zero表示一个空字段)：

int[][] start = {{0,1,2}, {4,5,3}, {7,8,6}};
int[][] target = {{1,2,3}, {1,5,6}, {7,8,0}};

这个数组进入了我的通用DFS类，它工作得很好。我正确地使用了其他任务。但是为了完整起见，这里是我的DFS类的basic部分：

private static boolean search(State node, State target) {
    if (node.equals(target))
        return true;

    for (State neighbour : node.getNeighbours()) {
        if (!visited.contains(neighbour)) {
            predMap.put(neighbour,node);
            visited.add(neighbour);
            if (search(neighbour, target)){
              return true;
            }
        }
    }
    return false;
}

因此，首先我的start数组将作为第一个参数传递，而我的target数组将作为第二个参数传递。

在我的State类中，我希望实现getNeighbours()方法，它应该返回所有可能的状态。在第一轮中，如下所示：

First:
|0|1|2|
|4|5|3|
|7|8|6|

Second (rotated zero):
|1|0|2|
|4|5|3|
|7|8|6|

etc...

这是我的问题。你怎么能这么做？它适用于前4个操作，但随后我得到一个异常(0或空字段不在异常位置，或者有两个零)。哪里出什么问题了？

@Override
public List<State> getNeighbours() {
    List<State> neighbours = new LinkedList<>();

    // possibles moves...
    final int startX = (freeX - 1 < 0) ? freeX : freeX - 1;
    final int startY = (freeY - 1 < 0) ? freeY : freeY - 1;
    final int endX = (freeX + 1 > N - 1) ? freeX : freeX + 1;
    final int endY = (freeY + 1 > N - 1) ? freeY : freeY + 1;

    for (int row = startX; row <= endX; row++) {
        for (int column = startY; column <= endY; column++) {
            int tmp = board[row][column];
            board[row][column] = board[freeX][freeY];
            board[freeX][freeY] = tmp;

            // Just show the table...
            System.out.println("=== BEFORE ===");
            for (int[] x : board) {
                System.out.println(Arrays.toString(x));
            }

            neighbours.add(new State(board, freeX + row, freeY + column));

            board[freeX][freeY] = board[row][column];
            board[row][column] = tmp;

            // Just show the table...
            System.out.println("=== AFTER ===");
            for (int[] x : board) {
                System.out.println(Arrays.toString(x));
            }
        }
    }

    return neighbours;    
}

完整代码https://gist.github.com/T0bbes/66d36326aa8878d5961880ce370ba82d

Answer 1

我检查了您的代码，得到这个例外的原因是，板数组由每个状态共享。您应该对该数组进行深度复制，您可以尝试以下代码：

public Board(int[][] board, int x, int y){
    if (board[x][y]!=0)
        throw new IllegalArgumentException("Field (" +x+","+y+") must be free (0).");
    this.board = new int[board.length][board[0].length];
    for (int i = 0; i < this.board.length; i++)
        for (int j = 0; j < this.board[i].length; j++)
            this.board[i][j] = board[i][j];
    this.freeX = x;
    this.freeY = y;
    this.N = board.length;
}

但是，在代码中仍然存在一些问题：

1. DFS可能会递归很多，并得到一个StackOverflow --您应该增加堆栈大小(-Xss100m适用于我)。增加堆栈大小后，您的代码可以输出一个解决方案，但它需要197144步.
2. 实际上，正如您所看到的，DFS只输出有效的解决方案(如果代码正确)，而不是最优解决方案。你应该试试BFS。