The misplaced-tiles heuristic is exact for the problem where a tile can move from square
A to square B. As this is a relaxation of the condition that a tile can move from square A to
square B if B is blank, Gaschnig’s heuristic canot be less than the misplaced-tiles heuristic.
As it is also admissible (being exact for a relaxation of the original problem), Gaschnig’s
heuristic is therefore more accurate.
If we permute two adjacent tiles in the goal state, we have a state where misplaced-tiles
and Manhattan both return 2, but Gaschnig’s heuristic returns 3.
To compute Gaschnig’s heuristic, repeat the following until the goal state is reached:
let B be the current location of the blank; if B is occupied by tile X (not the blank) in the
goal state, move X to B; otherwise, move any misplaced tile to B. Students could be asked to
prove that this is the optimal solution to the relaxed problem.