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.

Why use dfs ? I assume you want the shortest path so use bfs. — c0der, Jul 22 '18 at 05:44
@c0der sure thats an option and I am working on that but here I need help on fixing this code. Are you suggesting that DFS always results on stack overflow error? So don't use it? — Dangerous Scholar, Jul 22 '18 at 06:57
no, I was not relating to the stack overflow but to the choice of algorithm. — c0der, Jul 22 '18 at 07:04
I don't see how the solution post can be correct. `depth > 3000` returns false after the 2nd `for` loop — c0der, Jul 25 '18 at 05:38
Stack will collapse at 3000 and will retry. Hash map has pervious states so it wont try it again. It worked for me with the examples. — Dangerous Scholar, Jul 28 '18 at 05:37

c0der · Accepted Answer · 2018-07-22T08:49:06.490

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.

edited Jul 22 '18 at 08:49

answered Jul 22 '18 at 08:40

c0der

18,467
6
33
65

Thanks for the explanation. Does this mean that there is no way to fix the current code to get to the solution? – Dangerous Scholar Jul 23 '18 at 06:15
1

Well recursive solutions are always prone to StackOveflow. You could limit the recursion depth, and do the recursion in intervals (see examples [1](https://stackoverflow.com/a/46022542/3992939) , [2](https://stackoverflow.com/a/46128171/3992939), [3](https://stackoverflow.com/a/51336197/3992939) ). Wouldn't non - recursive solution be simpler? – c0der Jul 23 '18 at 08:19
Awesome! Thanks for the pointers. It works perfectly after stack-depth limiter. I agree, non-recursive solution is a good idea for this. – Dangerous Scholar Jul 23 '18 at 20:30

score 0 · Answer 2 · answered Jul 28 '18 at 03:18

Here is a version with limited recursion depth. It needs profiling (it is slow) but it works (tested with a range of test cases. Not fully debugged though):

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class LimitedDfs {

    private static final int DEPTH_LIMIT = 3000;
    private static final int BLANK = 9;

    private static int[][] directions = {
            {-1, 0},  //up
            { 0,-1},  //left
            { 0, 1},  //right
            { 1, 0}   //down
    };

    private static int[][] target = new int[][]{
        { 1,  2,  3},
        { 4,  5,  6},
        { 7,  8,  9}
    };

    private static State targetState = new State(target);

    public static void main(String[] args) {

        int[][] swap31 = new int[][] {
            {3,5,1},
            {6,2,4},
            {8,7,9}
        };

        isSolvable(swap31);
    }

    static boolean isSolvable(int[][] stateData) {

        State state = new State(stateData);
        List<State> tested = new ArrayList<>();
        LinkedList<State> toBeTested = new LinkedList<>();
        toBeTested.add(state);
        boolean solution = false;

        System.out.print("working ");
        while (! toBeTested.isEmpty()) {

            if ( isSolvable(toBeTested, tested, 0)){
                solution = true;
                break;
            }
            System.out.print(".");
        }

        System.out.print(" Tested "+ tested.size() + " states. ");

        if (solution) {
            System.out.println("\n       -> Solution exists ");
        }else{
            System.err.println("\n       -> Solution does not exist ");
        }

        return solution;
    }

    static boolean isSolvable(LinkedList<State> toBeTested, List<State> tested, int depth) {

        if((depth ++ > DEPTH_LIMIT) || toBeTested.isEmpty()) {
            return false;
        }

        //else get last element in stack
        State state = toBeTested.peek();

        if (state.equals(targetState)) {
            return true;
        }

        int added = 0;
        for(int[] dir : directions) {

            State newState = move(state, dir);
            if((newState != null)  && ! tested.contains(newState)) {
                toBeTested.add(newState);
                tested.add(newState);
                added++;
                break;
            }
        }

        if(added == 0) { // means state was fully explored, remove it
            toBeTested.remove(state);
        }

        return isSolvable(toBeTested, tested, depth);
    }

    private static State move(State state, int[] dir) {

        int[][] stateData = state.getState();
        int size = stateData.length;

        int[][] newArray = new int[size][size];
        int posY = 0, posX = 0;
        for (int y = 0; y < size; y++) {
            for (int x = 0; x < size; x++) {
                newArray[y][x] = stateData[y][x];
                if (stateData[y][x] == BLANK) {
                    posY = y;
                    posX = x;
                }
            }
        }

        if( isValidAddress(posY + dir[0], posX + dir[1], size, size)) {
            swap(newArray, posY, posX,posY+ dir[0], posX+ dir[1]);
            return new State(newArray);
        }

        return null;
    }

    private static void swap(int[][] arr, int y1, int x1, int y2, int x2) {
        int temp = arr[y1][x1];
        arr[y1][x1] = arr[y2][x2];
        arr[y2][x2] = temp;
    }

    private static boolean isValidAddress(int rowIndex,int colIndex,
            int numberOfRows, int numberOfCols) {

        if((rowIndex <0) || (rowIndex >= numberOfRows)||
                (colIndex <0) || (colIndex >= numberOfCols)) {
            return false;
        }

        return true;
    }
}

class State {

    private final int[][] state;
    private final int hash;

    State(int[][] state) {
        this.state = state;
        hash = serializeArray(state).hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {  return true;    }
        if (obj == null) {  return false;   }
        if (getClass() != obj.getClass()) {
            return false;
        }

        return hash == obj.hashCode();
    }

    @Override
    public int hashCode() {
        return hash;
    }

    int[][] getState() {
        return state;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for(int[] array : state) {
            sb.append(Arrays.toString(array))
            .append("\n");
        }
        return sb.toString();
    }

    private static String serializeArray(int[][] array) {

        StringBuilder sb = new StringBuilder();

        for (int[] elements : array) {
            for (int element : elements) {
                sb.append(element);
            }
        }
        return sb.toString();
    }
}

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

2 Answers2