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?