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.

Answer 2

If your heuristic it's admissible (and it is, check this) than A* always return optimal solution. Can be slower or faster (expand more or less nodes) but it returns the optimal solution.

So, cause your heuristic is admissible the problem must be in A* algorithm implementation.

In addition the fact that its first step it's different from the optimal one is meaningless: the algorithm can correctly performs backtrace to get the correct solution path in the future. All the open nodes are candidates for the next step, not only the child of the current node.