Exercise 3.39 [Gaschnig-h-exercise]

On page Gaschnig-h-page , we defined the relaxation of the 8-puzzle in which a tile can move from square A to square B if B is blank. The exact solution of this problem defines Gaschnig’s heuristic @Gaschnig:1979. Explain why Gaschnig’s heuristic is at least as accurate as $h_1$ (misplaced tiles), and show cases where it is more accurate than both $h_1$ and $h_2$ (Manhattan distance). Explain how to calculate Gaschnig’s heuristic efficiently.