Running out of java heap space- 15 puzzle problem

G’day all, I tried the solution for eight puzzle problem posted here by joel Neely and played around with it and modified it so that can be used to solve for higher grids[Changed the String representation of the grid to two dimensional integer representation and modified the logic accordingly]. However the modified code can solve the 3×3 grids but quickly run out of heap space for 4×4 grid. I guess this is the restriction caused by the algorithm used which i think is some variation of branch and bound and not that of java. If my assumptions are right, can someone suggest any other good algorithms for solving this problem?. If not, please hint what can be done to make this program work for higher order grids.

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

class EightPuzzle {

    //Queue<Integer[][]> agenda = new LinkedList<Integer[][]>();    // Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
    //Map<Integer[][],Integer> stateDepth = new HashMap<Integer[][], Integer>(); // HashMap is used to ignore repeated nodes
    //Map<Integer[][],Integer[][]> stateHistory = new HashMap<Integer[][],Integer[][]>(); // relates each position to its predecessor
    Map<String,String> stateHistory = new HashMap<String,String>(); // relates each position to its predecessor
    Map<String,Integer> stateDepth = new HashMap<String,Integer>();
    Queue<Integer[][]> agenda=new LinkedList<Integer[][]>();
    final int GRIDSIZE=4;
    int row=0,col=0;
    public static void main(String args[]){

       // Integer[][] str="087465132";                                 // Input the Board State as a Integer[][] with 0 as the Blank Space
        Integer init[][]={{1,3,12,4},{2,9,10,7},{0,14,8,15},{5,6,13,11}};
        //Integer init[][]={{0,8,7},{4,6,5},{1,3,2}};
        EightPuzzle e = new EightPuzzle();              // New Instance of the EightPuzzle

        e.add(init,null);                                                   // Add the Initial State

        while(!e.agenda.isEmpty()){
            Integer[][] currentState = e.agenda.remove();
            e.up(currentState);                                       // Move the blank space up and add new state to queue
            e.down(currentState);                                     // Move the blank space down
            e.left(currentState);                                     // Move left
            e.right(currentState);                          // Move right and remove the current node from Queue
        }

        System.out.println("Solution doesn't exist");
    }

    //Add method to add the new Integer[][] to the Map and Queue
    void add(Integer newState[][], Integer oldState[][]){
        if(!stateDepth.containsKey(convertToString(newState))){
            int newValue = oldState == null ? 0 : stateDepth.get(convertToString(oldState)) + 1;
            stateDepth.put(convertToString(newState), newValue);
            agenda.add(newState);
            stateHistory.put(convertToString(newState), convertToString(oldState));
        }
    }

    /* Each of the Methods below Takes the Current State of Board as Integer[][]. Then the operation to move the blank space is done if possible.
      After that the new Integer[][] is added to the map and queue.If it is the Goal State then the Program Terminates.
     */
    void up(Integer[][] currentState){
        Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
        getIndicesOfZero(currentState, nextState);
        if(row!=0){
            nextState[row-1][col]=currentState[row][col];
            nextState[row][col]=currentState[row-1][col];
            checkCompletion(currentState, nextState);
        }
    }

    /**
     * @param currentState
     */
    /**
     * @param currentState
     */
    void down(Integer[][] currentState){
        Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
        getIndicesOfZero(currentState, nextState);
        if(row!=GRIDSIZE-1){
            nextState[row+1][col]=currentState[row][col];
            nextState[row][col]=currentState[row+1][col];  
            checkCompletion(currentState, nextState);
        }
    }
    void left(Integer[][] currentState){
        Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
        getIndicesOfZero(currentState, nextState);
        if(col!=0){
            nextState[row][col-1]=currentState[row][col];
            nextState[row][col]=currentState[row][col-1];
            checkCompletion(currentState, nextState);
        }
    }
    void right(Integer[][] currentState){
        Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
        getIndicesOfZero(currentState, nextState);
        if(col!=GRIDSIZE-1){
            nextState[row][col+1]=currentState[row][col];
            nextState[row][col]=currentState[row][col+1];
            checkCompletion(currentState, nextState);
        }
    }

    private void checkCompletion(Integer[][] oldState, Integer[][] newState) {
        add(newState, oldState);
        Integer[][] completeState={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}};
        //Integer[][] completeState={{1,2,3},{4,5,6},{7,8,0}};
        boolean equality=true;
        outer:for(int i=0;i<GRIDSIZE;i++){
            for(int j=0;j<GRIDSIZE;j++){
                if(newState[i][j]!=completeState[i][j]){
                    equality=false;
                    break outer;
                }
            }
        }

        if(equality){
            System.out.println("Solution Exists at Level "+stateDepth.get(convertToString(newState))+" of the tree");
            String traceState = convertToString(newState);
            while (traceState != null) {   
                System.out.println(traceState + " at " + stateDepth.get(traceState));
                traceState = stateHistory.get(traceState);
            }
            System.exit(0);

        }
    }
    String convertToString(Integer[][] a){
        String str="";
        if(a!=null){
            for(int i=0;i<GRIDSIZE;i++){
                for(int j=0;j<GRIDSIZE;j++){
                    str+=a[i][j];
                }
            }
        }
        else{
            str=null;
        }
        return str;
    }
    void getIndicesOfZero(Integer[][] currentState,Integer[][] nextState){
        for(int i=0;i<GRIDSIZE;i++){
            for(int j=0;j<GRIDSIZE;j++){
                nextState[i][j]=currentState[i][j];
            }
        }
        outer:for(int i=0;i<GRIDSIZE;i++){
            for(int j=0;j<GRIDSIZE;j++){
                if(currentState[i][j]==0){
                    row=i;
                    col=j;
                    break outer;
                }
            }
        }

    }
}

Thanks in advance, paul.

Answer

Your algorithm lacks a heuristic. In other words, it’s exploring the search space with no guidance. For the 15-puzzle, that space is quite large, close to 3**(depth of the solution).

If you order your queue by the sum of the Manhattan distance of each tile from its destination, it might be sufficient to make it solvable. At each step, expand the item on the agenda with the least “error”.

Also, are you sure the start state you’ve chosen is solvable? If you randomly order the tiles, you only have a 50-50 chance.

Finally, you might switch from Integer to byte to save memory. How much depends on the java implementation, but since Integer is a class and byte a primitive type, it could be significant.

Updated