java - 我如何使用深度优先搜索来解决这个难题？

Question

所以我所做的就是制作一个看起来像这样的滑动拼图:

1 0 3
4 2 6
7 5 8

其中 0 表示空白空间，我通过邻接矩阵将其转换为图形。然后我想做的是搜索图表并找到 0 的值，然后从该值开始，执行 DFS 并找到从 0 到右下角的路径，当解决的难题看起来像这样时:

1 2 3
4 5 6
7 8 0

这是应该执行 DFS 的代码:

public static boolean SolveNinePuzzle(int[][] B){
        //first section of the code makes the adjacency matrix
        int[][] G = new int[9][9];
        int temp2;
        int temp1;
        for (int i = 0; i < 3; i++){
            for (int j = 0; j < 3; j++){
                getBoardFromIndex(i);
                if (i < 2){
                    temp1 = B[i][j];
                    temp2 = B[i+1][j];
                    G[temp2][temp1] = 1;
                    G[temp1][temp2] = 1;
                    getIndexFromBoard(B);
                }
                if (i > 0){
                    temp1 = B[i][j];
                    temp2 = B[i-1][j];
                    G[temp2][temp1] = 1;
                    G[temp1][temp2] = 1;
                    getIndexFromBoard(B);
                }
                if (j < 2){
                    temp1 = B[i][j];
                    temp2 = B[i][j+1];
                    G[temp2][temp1] = 1;
                    G[temp1][temp2] = 1;
                    getIndexFromBoard(B);
                }
                if (j > 0){
                    temp1 = B[i][j];
                    temp2 = B[i][j-1];
                    G[temp2][temp1] = 1;
                    G[temp1][temp2] = 1;
                    getIndexFromBoard(B);
                }
            }
        }
        printGraph(G);
        System.out.println();
        //Finds out where 0 is and moves the tiles either up down or left or right depending on
        int l = B.length;
        int temp;
        boolean isSolved = true;
        printBoard(B);
        int n = G.length;
        int[] visited = new int[n];
        int visits = 0;
        int c = 0; 
        visited[c] = 1;
        for (int k = 0; k < visited.length; k++) {
            if (visited[k] == 0 && G[c][k] == 1){
                visited[c] = 1;
                c = k;
                k = 0;
            }
        }       

现在它应该经过所有相邻的顶点。我还没有的是一种在板上交换值的方法，而且当它到达右下角时我也没有搜索停止。基本上，我如何将 DFS 算法应用到带有板的图形上。

Answer 1

从评论中重复:

没有堆栈的 DFS 或没有队列的 BFS 是不存在的。您提供的 DFS 实现使用系统堆栈，这是递归的结果，因此我们不需要显式定义堆栈。由于任何函数调用都会创建一个系统堆栈(请参阅，代码如何执行，或者调用函数时会发生什么)，并且没有(固有的)使用队列的方式，因此将始终在 BFS 的实现中声明一个队列。

现在，如果您想使用 BFS 解决这个问题，我建议您这样做:

首先，为访问状态创建一个数组，这样就不会每次都进行冗余调用。有9个!可以存储为字符串(键)、(bool)值映射的可能性，表示是否访问了棋盘状态。

将初始状态标记为已访问。可以为每个棋盘状态进行 2(角)、3(边)或 4(中心)移动。进行这些移动并将这些状态推送到队列中，弹出当前状态(并将其标记为已访问)。这样做直到获得目标状态。 BFS 将自行确保如果您达到目标状态，它将以最少的移动。