Manhattan distance in A*

Question

I am implementing a NxN puzzle solver using A* search algorithm and using Manhattan distance as a heuristic and I've run into a curious bug (?) which I can't wrap my head around.

Consider these puzzles (0 element being blank space):
(initial)

1 0 2
7 5 4
8 6 3

(goal)

1 2 3
4 5 6
7 8 0

The minumum number of moves to reach solution from initial state is 11. However, my solver, reaches goal in 17 moves.

And therein lies the problem - my puzzle solver mostly solves the solvable puzzles in a correct (minimum) number of moves but for this particular puzzle, my solver overshoots the minimum number of moves and I think I've nailed down the problem to a miscalculation of Manhattan distance in this particular case.

At this link you can see what my solver is doing (on the right) and what a tried-n-tested solver is doing (Brian Borowski's excellent solver, available here).

In the very first move, Brian's solver immediately chooses solution that pushes element 5 up, but my solver has other ideas, and on the stacktrace (given on the link), my solver chooses solution which pushes 2 to the left (since that board's Manhattan distance is lower, the board is on the front of priority queue). I can't see what is the problem and I can't blame my Manhattan distance calculation, since it correctly solves a number of other 3x3 puzzles.

Here is how I calculate the Manhattan distance of a given Board:

/**
 * Calculates sum of Manhattan distances for this board and stores it in private field to promote immutability.
 */
private void calculateManhattanDistance() {
    int manhattanDistanceSum = 0;
    for (int x = 0; x < N; x++) // x-dimension, traversing rows (i)
        for (int y = 0; y < N; y++) { // y-dimension, traversing cols (j)
            int value = tiles[x][y]; // tiles array contains board elements
            if (value != 0) { // we don't compute MD for element 0
                int targetX = (value - 1) / N; // expected x-coordinate (row)
                int targetY = (value - 1) % N; // expected y-coordinate (col)
                int dx = x - targetX; // x-distance to expected coordinate
                int dy = y - targetY; // y-distance to expected coordinate
                manhattanDistanceSum += Math.abs(dx) + Math.abs(dy); 
            } 
        }
    manhattanDistance = manhattanDistanceSum;
}

I would appreciate any insight or idea you may have.

If any additional code is needed, I'll post it right away.

Answer 1

I was stuck in the same place sometime back where I was solving this in 17 moves.The problem was that I was only using heuristic h(n) for the A* algorithm and whereas for choosing the next node A* uses manhattan distance(heuristic) + pathcost (cost to reach the node from root called as g(n)) to make the choice. Once you plug in this to the algorithm it works like a charm.

Hope this helps someone who is stuck in the same place.