We defined the relaxation of the 8-puzzle in which a
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 (misplaced tiles), and show cases where it is more accurate than both h1 and h2 (Manhattan distance). Can you suggest a way to calculate Gaschnig’s heuristic efficiently?