Manhattan Distance in 8’s
Manhattan distance in 8’s puzzle is NOT a good heuristic
It can be misled
- Suppose we have a small Manhattan distance for move A
- but any solution for move A must reverse move A eventually (e.g. to allow a vital move B)
- We have in reality made the solution 2 moves longer
- moving piece A and then putting it back again
- Heuristic thinks we are closer to a solution
Infinite loops can occur in Best First + Manhattan