Solve n-puzzle in Java

Question

I'm trying to implement a program to solve the n-puzzle problem.
I have written a simple implementation in Java that has a state of the problem characterized by a matrix representing the tiles. I am also able to auto-generate the graph of all the states giving the starting state. On the graph, then, I can do a BFS to find the path to the goal state.
But the problem is that I run out of memory and I cannot even create the whole graph. I tried with a 2x2 tiles and it works. Also with some 3x3 (it depends on the starting state and how many nodes are in the graph). But in general this way is not suitable.
So I tried generating the nodes at runtime, while searching. It works, but it is slow (sometimes after some minutes it still have not ended and I terminate the program).
Btw: I give as starting state only solvable configurations and I don't create duplicated states.
So, I cannot create the graph. This leads to my main problem: I have to implement the A* algorithm and I need the path cost (i.e. for each node the distance from the starting state), but I think I cannot calculate it at runtime. I need the whole graph, right? Because A* does not follow a BFS exploration of the graph, so I don't know how to estimate the distance for each node. Hence, I don't know how to perform an A* search.
Any suggestion?

EDIT

State:

private int[][] tiles;
private int pathDistance;
private int misplacedTiles;
private State parent;

public State(int[][] tiles) {
    this.tiles = tiles;
    pathDistance = 0;
    misplacedTiles = estimateHammingDistance();
    parent = null;
}

public ArrayList<State> findNext() {
    ArrayList<State> next = new ArrayList<State>();
    int[] coordZero = findCoordinates(0);
    int[][] copy;
    if(coordZero[1] + 1 < Solver.SIZE) {
        copy = copyTiles();
        int[] newCoord = {coordZero[0], coordZero[1] + 1};
        switchValues(copy, coordZero, newCoord);
        State newState = checkNewState(copy);
        if(newState != null)
            next.add(newState);
    }
    if(coordZero[1] - 1 >= 0) {
        copy = copyTiles();
        int[] newCoord = {coordZero[0], coordZero[1] - 1};
        switchValues(copy, coordZero, newCoord);
        State newState = checkNewState(copy);
        if(newState != null)
            next.add(newState);
    }
    if(coordZero[0] + 1 < Solver.SIZE) {
        copy = copyTiles();
        int[] newCoord = {coordZero[0] + 1, coordZero[1]};
        switchValues(copy, coordZero, newCoord);
        State newState = checkNewState(copy);
        if(newState != null)
            next.add(newState);
    }
    if(coordZero[0] - 1 >= 0) {
        copy = copyTiles();
        int[] newCoord = {coordZero[0] - 1, coordZero[1]};
        switchValues(copy, coordZero, newCoord);
        State newState = checkNewState(copy);
        if(newState != null)
            next.add(newState);
    }
    return next;
}

private State checkNewState(int[][] tiles) {
    State newState = new State(tiles);
    for(State s : Solver.states)
        if(s.equals(newState))
            return null;
    return newState;
}

@Override
public boolean equals(Object obj) {
    if(this == null || obj == null)
        return false;
    if (obj.getClass().equals(this.getClass())) {
        for(int r = 0; r < tiles.length; r++) { 
            for(int c = 0; c < tiles[r].length; c++) {
                if (((State)obj).getTiles()[r][c] != tiles[r][c])
                    return false;
            }
        }
            return true;
    }
    return false;
}

Solver:

public static final HashSet<State> states = new HashSet<State>();

public static void main(String[] args) {
    solve(new State(selectStartingBoard()));
}

public static State solve(State initialState) {
    TreeSet<State> queue = new TreeSet<State>(new Comparator1());
    queue.add(initialState);
    states.add(initialState);
    while(!queue.isEmpty()) {
        State current = queue.pollFirst();
        for(State s : current.findNext()) {
            if(s.goalCheck()) {
                s.setParent(current);
                return s;
            }
            if(!states.contains(s)) {
                s.setPathDistance(current.getPathDistance() + 1);
                s.setParent(current);
                states.add(s);
                queue.add(s);
            }
        }
    }
    return null;
}

Basically here is what I do:
- Solver's solve has a SortedSet. Elements (States) are sorted according to Comparator1, which calculates f(n) = g(n) + h(n), where g(n) is the path cost and h(n) is a heuristic (the number of misplaced tiles).
- I give the starting configuration and look for all the successors.
- If a successor has not been already visited (i.e. if it is not in the global set States) I add it to the queue and to States, setting the current state as its parent and parent's path + 1 as its path cost.
- Dequeue and repeat.

I think it should work because:
- I keep all the visited states so I'm not looping.
- Also, there won't be any useless edge because I immediately store current node's successors. E.g.: if from A I can go to B and C, and from B I could also go to C, there won't be the edge B->C (since path cost is 1 for each edge and A->B is cheaper than A->B->C).
- Each time I choose to expand the path with the minimum f(n), accordin to A*.

But it does not work. Or at least, after a few minutes it still can't find a solution (and I think is a lot of time in this case).
If I try to create a tree structure before executing A*, I run out of memory building it.

EDIT 2

Here are my heuristic functions:

private int estimateManhattanDistance() {
    int counter = 0;
    int[] expectedCoord = new int[2];
    int[] realCoord = new int[2];
    for(int value = 1; value < Solver.SIZE * Solver.SIZE; value++) {
        realCoord = findCoordinates(value);
        expectedCoord[0] = (value - 1) / Solver.SIZE;
        expectedCoord[1] = (value - 1) % Solver.SIZE;
        counter += Math.abs(expectedCoord[0] - realCoord[0]) + Math.abs(expectedCoord[1] - realCoord[1]);
    }
    return counter;
}

private int estimateMisplacedTiles() {
    int counter = 0;
    int expectedTileValue = 1;
    for(int i = 0; i < Solver.SIZE; i++)
        for(int j = 0; j < Solver.SIZE; j++) {
            if(tiles[i][j] != expectedTileValue)
                if(expectedTileValue != Solver.ZERO)
                    counter++;
            expectedTileValue++;
        }
    return counter;
}

If I use a simple greedy algorithm they both work (using Manhattan distance is really quick (around 500 iterations to find a solution), while with number of misplaced tiles it takes around 10k iterations). If I use A* (evaluating also the path cost) it's really slow.

Comparators are like that:

public int compare(State o1, State o2) {
    if(o1.getPathDistance() + o1.getManhattanDistance() >= o2.getPathDistance() + o2.getManhattanDistance())
        return 1;
    else
        return -1;
}

EDIT 3

There was a little error. I fixed it and now A* works. Or at least, for the 3x3 if finds the optimal solution with only 700 iterations. For the 4x4 it's still too slow. I'll try with IDA*, but one question: how long could it take with A* to find the solution? Minutes? Hours? I left it for 10 minutes and it didn't end.

Answer 1

There is no need to generate all state space nodes for solving a problem using BFS, A* or any tree search, you just add states you can explore from current state to the fringe and that's why there is a successor function. If BFS consumes much memory it is normal. But I don't know exactly fro what n it would make problem. Use DFS instead. For A* you know how many moves you made to come to current state and you can estimate moves need to solve problem, simply by relaxing problem. As an example you can think that any two tiles can replace and then count moves needed to solve the problem. You heuristic just needs to be admissible ie. your estimate be less then actual moves needed to solve the problem.