On page 108, we defined the relaxation of the &-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 hl

(misplaced tiles), and show cases where it is more accurate than both hl and h2 (Manhattan distance). Can you suggest a way to calculate Gaschnig's heuristic efficiently?