java - n-puzzle DFS 解决方案适用于 2X2，但适用于 3X3 StackOverflowError

Question

我的 npuzzle 解决方案适用于 2x2，但适用于 3x3 时出现堆栈溢出错误。我不知道出了什么问题。我正在使用 DFS 来检查是否有任何路径有解决方案。算法， - 左、右、上、下移动棋子。 - 每次检查状态是否已被访问。 - 如果未访问过，则标记已访问并检查其是否与目标状态匹配。我相信堆栈应该能够容纳所有状态，它应该只有 181400 个状态，对吗？

请大家帮忙!

public class PuzzleSolvable {

public static final int N = 3;
public static int[][] s2 = new int[][]{{8, 2, 1},
                                       {-1, 4, 3},
                                       {7, 6, 5}};

public static void main(String[] args) {
    int[][] stage1 = new int[][]{ //needs 5 swaps
                                  {1, 2, 3},
                                  {4, 5, 6},
                                  {7, 8, -1}
    };

    /*int[][] stage1 = new int[][]{{1, 2},
                                 {4, -1}};
    int[][] stage2 = new int[][]{{-1, 1},
                                 {4, 2}};*/
    Map<String, Boolean> map = new HashMap<>();
    boolean solution = false;
    for (int i = 0; i <= 181440; i = i + 3000) {
        if (isSolvable(stage1, map, i)) {
            solution = true;
            break;
        }
    }

    if (solution) {
        System.out.println("Solution exists");
    }else{
        System.out.println("Solution does not exist");
    }
}

static boolean isSolvable(int[][] s1, Map<String, Boolean> map, int depth) {
    if (depth > 3000) {
        return false;
    }
    depth++;
    System.out.println(serializeArray(s1));
    System.out.println(map.size());
    if (map.get(serializeArray(s1)) != null) {
        return false;
    }
    if (equals(s1, s2)) {
        return true;
    }
    map.put(serializeArray(s1), true);

    return isSolvable(move(s1, 0), map, depth) ||
           isSolvable(move(s1, 1), map, depth) ||
           isSolvable(move(s1, 2), map, depth) ||
           isSolvable(move(s1, 3), map, depth);
}

static String serializeArray(int[][] arr) {
    String s = "";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            s = s + arr[i][j];
        }
    }
    return s;
}

static boolean equals(int[][] s1, int[][] s2) {

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (s1[i][j] != s2[i][j]) {
                return false;
            }
        }
    }
    return true;
}

static int[][] move(int[][] arr, int direction) {
    int[][] array = new int[N][N];
    int posx = 0, posy = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            array[i][j] = arr[i][j];
            if (arr[i][j] == -1) {
                posx = i;
                posy = j;
            }
        }
    }

    switch (direction) {
        case 0://right
            if (posy < N - 1) {
                System.out.println("Swap right");
                swap(array, posx, posy, posx, posy + 1);
            }
            break;
        case 1://left
            if (posy > 0) {
                System.out.println("Swap left");
                swap(array, posx, posy, posx, posy - 1);
            }
            break;
        case 2://up
            if (posx > 0) {
                System.out.println("Swap up");
                swap(array, posx, posy, posx - 1, posy);
            }
            break;
        case 3://down
            if (posx < N - 1) {
                System.out.println("Swap down");
                swap(array, posx, posy, posx + 1, posy);
            }
            break;
    }
    return array;
}

static void swap(int[][] arr, int posx, int posy, int x, int y) {
    int temp = arr[posx][posy];
    arr[posx][posy] = arr[x][y];
    arr[x][y] = temp;
}}

编辑:使用递归深度限制器实现的工作版本更新代码。

Answer 1

我认为堆栈溢出确实有道理。
如果您使用

表示的目标进行测试

static int[][] s2 = new int[][]{
    { 1,  2, 3},
    { 4, -1, 5},
    { 6,  7, 8}
};

并将初始状态设置为

int[][] stage5 = new int[][]{ //needs 5 swaps
    { 2,  3,   5},
    { 1,  4,  -1},
    { 6,  7,   8}
};

需要 5 次交换才能获得目标，isSolvable 被调用 54 次，无一异常(exception)。
如果您将初始状态设置为

int[][] stage6 = new int[][]{ //needs 6 swaps
    { 2,  3,  5},
    { 1,  4,  8},
    { 6,  7, -1}
};

需要 6 次交换才能获得目标，isSolvable 被调用大约 12000 次，并抛出 StackOverflowError。

即使是简单的休息

recusiveTest(stage6,  new Random());

//overflows after less than 5k invokes
private static boolean recusiveTest(int[][] array, Random rand){
    System.out.println("counter " +isSolvedCounter++);
    array[rand.nextInt(2)][rand.nextInt(2)] = 0;
    return recusiveTest(array, rand);
}

运行次数少于 5000 次后抛出 StackOverflowError。
非递归 dfs 解决方案会更可靠。