Related Problems: N-Puzzle Type:heuristic function

The Manhattan Distance is the distance between two points measured along axes at right angles. The name alludes to the grid layout of the streets of Manhattan, which causes the shortest path a car could take between two points in the city.

For the 8-puzzle, if xi(s) and yi(s) are the x and y coordinates of tile i in state s, and if upper-line(xi) and upper-line (yi) are the x and y coordinates of tile i in the goal state, the heuristic is:

formula.JPG


In the following example the Manhattan Distance is 3+6=9 moves:


manhattan_distance_example.png

Random 15-puzzle instances were first solved optimally using IDA* with Manhattan distance heuristic (Korf, 1985). Optimal solution lengths average 53 moves, and on average 400 million nodes were generated.

The limitation of the Manhattan Distance heuristic is that it considers each tile independently, while in fact tiles interfere with each other. Higher accuracy can be achieved by combining other heuristics, such as the Linear Conflict Heuristic.


The Manhattan Distance heuristic is admissble.