Related Problems: N-Puzzle Type:heuristic function

h = Number of tiles out of row + number of tiles out of column

For example, in the following cenario The heuristic value is:
2 tiles out of column + 1 tile out of row = 3


manhattan_distance_example.png

This heuristic is admissible.