Related Problems: N-Puzzle Type:heuristic function

h = Number of tiles that are not in the final position (not counting the blank)

For example, in the following cenario The Misplaced Distance is 1+1=2 moves

manhattan_distance_example.png

This heuristic is admissible.