Iterative Deepening A Star (IDA*) to solve n-puzzle (sliding puzzle) in Java

Question

I've implemented a program able to solve the n-puzzle problem with A*. Since the space of the states is too big I cannot precompile it and I have to calculate the possible states at runtime. In this way A* works fine for a 3-puzzle, but for a 4-puzzle can take too long. Using Manhattan distance adjusted with linear conflicts, if the optimal solution requires around 25 moves is still fast, around 35 takes 10 seconds, for 40 takes 180 seconds. I haven't tried more yet.
I think that's because I must keep all visited states, since I'm using functions admissible but (I think) not consistent (i tried also with Hamming and Gaschnig distances and a few more). Since the space of the solution is a graph the heuristic must also be consistent, otherwise the algorithm can loop or be not optimal. That's why I keep all visited nodes (it's also written in the book "AI: A modern approach"). But anyway, this storage does not slow at all. What slows is keeping the queue of nodes to be visited ordered.
So I decided to try IDA* that, as I saw, does not require this storage (but still I have to keep all visited states to avoid loops). It's faster for solutions that require 35 or less moves, but for 40 it's much slower.
Here is my code. Am I doing something wrong?

public static State solveIDAStar(State initialState) {
    int limit = initialState.getManhattanDistance() + 2 * initialState.getLinearConflicts();
    State result = null;
    while(result == null) {
        visitedStates.add(initialState); // It's a global variable
        result = limitedSearch(initialState, limit);
        limit = newLimit;
        visitedStates.clear();
    }
    return result;
}

public static State limitedSearch(State current, int limit) {
    for(State s : current.findNext()) {
        if(s.equals(GOAL)) {
            s.setParent(current);
            return s;
        }
        if(!visitedStates.contains(s)) {
            s.setPathCost(current.getPathCost() + 1);
            s.setParent(current);
            int currentCost = s.getManhattanDistance() + 2 * s.getLinearConflicts() + s.getPathCost();
            if(currentCost <= limit) {
                visitedStates.add(s);
                State solution = limitedSearch(s, limit);
                if(solution != null)
                    return solution;
            } else {
                if(currentCost < newLimit)
                    newLimit = currentCost;
            }
        }
    }
    return null;
}

Solution

Old stuff moved down.

Changes so that newLimit can skip steps (the bestSolution stuff):

State bestSolution; // add this global

public static State solveIDAStar(State initialState) {
    int limit = initialState.getManhattanDistance() + 2 * initialState.getLinearConflicts();
    bestSolution = null; // reset global to null
    State result = null;
    while(result == null) {
        visitedStates.add(initialState); // It's a global variable
        newLimit = INFINITY;
        result = limitedSearch(initialState, limit);
        limit = newLimit;
        visitedStates.clear();
    }
    return result;
}

public static State limitedSearch(State current, int limit) {
    for(State s : current.findNext()) {
        if(s.equals(GOAL)) {
            s.setParent(current);
            return s;
        }
        if(!visitedStates.contains(s)) {
            s.setPathCost(current.getPathCost() + 1);
            s.setParent(current);
            int currentCost = s.getManhattanDistance() + 2 * s.getLinearConflicts() + s.getPathCost();
            if(currentCost <= limit) {
                visitedStates.add(s);
                State solution = limitedSearch(s, limit);
                if(solution != null &&
                   (bestSolution == null || solution.getPathCost() < bestSolution.getPathCost()))
                        bestSolution = solution; // cache solution so far
            } else {
                if(currentCost < newLimit)
                    newLimit = currentCost;
            }
        }
    }
    return null;
}

---

Original answer

So I found an open source implementation. Miraculously, it is also in java.

The application can be tested here: http://n-puzzle-solver.appspot.com/

And the source code specifically relevant is: http://code.google.com/p/julien-labs/source/browse/trunk/SlidingPuzzle/src/be/dramaix/ai/slidingpuzzle/server/search/IDAStar.java

Not sure how much the 1st change suggested below might change the time taken, but I am quite sure that you need to make the 2nd change.

---

First change

By comparing the code, you will find that this function

private Node depthFirstSearch(Node current, int currentCostBound, State goal)

is basically your function here

public static State limitedSearch(State current, int limit)

and Julien Dramaix's implementation doesn't have:

if(!visitedStates.contains(s)) {
    ...
    visitedStates.add(s);

So take those two lines out to test.

---

2nd change

Your function public static State solveIDAStar(State initialState) does something weird in the while loop.

After you fail once, you set the maximum depth (limit) to infinity. Basically, 1st iteration, you try find a solution as good as your heuristic. Then you try to find any solution. This is not iterative deepening.

Iterative deepening means every time you try, go a little bit deeper.

Indeed, looking at the while loop in public PuzzleSolution resolve(State start, State goal), you will find nextCostBound+=2;. That means, every time you try, try find solutions with up to 2 more moves.

---

Otherwise, everything else looks similar (although your exact implementation of the State class might be slightly different).

If it works better, you might also want to try some of the other heuristics at http://code.google.com/p/julien-labs/source/browse/#svn%2Ftrunk%2FSlidingPuzzle%2Fsrc%2Fbe%2Fdramaix%2Fai%2Fslidingpuzzle%2Fclient.

The heuristics are found in the server/search/heuristic folder.