n-puzzle DFS solution works for 2X2 but StackOverflowError for 3X3

Question

My solution for npuzzle works with 2x2 but stack over flow error with 3x3. I am not able to figure out whats wrong. I am using DFS to check if any of the path has the solution. Algorithm, - Move piece left, right, up & down. - For each check if state is already visited . - if not visited mark visited and check if it matches the goal state. I believed that the stack should be able to hold all the states, it should be only 181400 states right?

Any help please!

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;
}}

Edited: Code updated with working version implemented using recursion depth limiter.

Answer 1

I think stack overflow does make sense.
If you test it with a target represented by

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

and set initial state to

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

which requires 5 swaps to get the target, isSolvable is invoked 54 times with no exception.
If you set initial state to

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

which requires 6 swaps to get the target, isSolvable is invoked about 12000 times, and throws StackOverflowError.

Even a simple rest like

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);
}

throws StackOverflowError after less than 5000 runs.
A non recursive dfs solution would be more solid.