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?