A* 8 puzzle written in Java not working for certain initial states

Question

I had to implement an 8 puzzle solver utilizing the A* algorithm with two heuristics. The first heuristic was just the sum of the out-of-place tiles, the second is the sum of the Manhattan distances of all tiles from the goal state, which we are defining as:

0 1 2
3 4 5
6 7 8

We given were sample tests of varying depths. My implementation using the first heuristic passes all of these cases, but the second heuristic does not pass certain test cases once it reaches depths of 14:

 (52) !Test Case failed! for initialState:
3 1 5 
6 0 7 
8 2 4
Expected depth of 14 but got 16

(12) !Test Case failed! for initialState:
4 1 5 
3 2 7 
0 8 6
Expected depth of 16 but got 18

(39) !Test Case failed! for initialState:
2 5 7 
3 4 1 
6 8 0
Expected depth of 16 but got 18

(There are more failed tests, these are just the first three) Since it seems to work for all cases when I use the first heuristic, I'm guessing it's something wrong with the second heuristic. Here is my abstract "node" class:

public EightPuzzleState(int[] state, EightPuzzleState goalState, EightPuzzleState previousState) {
    this.state = new int[NUM_SPACES];
    try {   
        System.arraycopy(state, 0, this.state, 0, NUM_SPACES);
    }catch(ArrayIndexOutOfBoundsException e){
        e.printStackTrace();
    }
    this.previousState = previousState;
    setCost(goalState);

}
private void setCost(EightPuzzleState goalState) {
    if(goalState == null) {
        System.out.println("Cost is 0- no goal state defined");
        cost = 0;
    }
    else {
        cost = calcCost(goalState);  
    }
}

private int calcCost(EightPuzzleState goalState) {
    int sum = 0;
    for(int i = 0; i < NUM_SPACES; i++) {
        sum+=heuristic(goalState, i);
    }
    if(previousState == null) {
        //System.out.println("No previous parent defined, 0 pathCost");
        pathCost = 0;
    }
    else {
        pathCost = previousState.getPathCost()+1;
    }
    return sum + pathCost;

And here is the node class that utilizes the second heuristic:

    //In EightPuzzleStateH2 class, which extends EightPuzzleState
    @Override
    protected int heuristic(EightPuzzleState goalState, int currentIndex) {
        int currentValue = this.getState()[currentIndex];
        int[] goalStateArray = goalState.getState();
        int i = 0;

        while(currentValue != goalStateArray[i]) { 
            i++;
        }

        return calcManhattenDistance(currentIndex,i);
    }

    private int calcManhattenDistance(int currentIndex, int goalIndex) {
        int xDistance = Math.abs((currentIndex % NUM_SPACES_PER_ROW) - (goalIndex % NUM_SPACES_PER_ROW));
        int yDistance = Math.abs((currentIndex / NUM_SPACES_PER_ROW) - (goalIndex / NUM_SPACES_PER_ROW));
        return (xDistance+yDistance);

    }

Any insight would be helpful- if the issue isn't within the second heuristic, then I'm really going to be stumped since the first heuristic worked flawlessly!

Answer 1

I was able to fix this issue by modifying my hashcode function for my EightPuzzleState class.

Also, when calculating the heuristic, I was including the hole in the calculation, but the hole should not be included in the cost calculation. This was not related to the problem I was having, but for the sake of other readers I am addressing it here.