Manhattan distance in A*

Question

I am implementing an 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 elements being blank space):

(initial)

1 0 2

7 5 4

8 6 3

(goal)

1 2 3

4 5 6

7 8 0

The minimum number of moves to reach a solution from the initial state is 11. However, my solver reaches the 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 a solution that pushes element 5 up, but my solver has other ideas, and on the stack trace (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

The main mistake you have http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.htmldone is that you have only used the heuristic h(n) for the A* algorithm and whereas for choosing the next node A* uses manhattan distance(heuristic) + pathcost (the cost to reach the node from the root called as g(n)) to make the choice. Once you plug in this to the algorithm it works fine. For more information regarding the heuristics, refer the following link:

If you are looking to learn more about Artificial Intelligence then you visit Artificial Intelligence Tutorial. Also, if you are appearing for job profiles of AI Engineer or AI Expert then you can prepare for the interviews on Artificial Intelligence Interview Questions.