4.9 We gave two simple heuristics for the 8-puzzle: Manhattan distance and misplaced tiles.

Several heuristics in the literature purport to be better than either of these. (See, for example, Nilsson

(1971) for additional improvements on Manhattan distance, and Mostow and Prieditis (1989)

for heuristics derived by semimechanical methods.) Test these claims by implementing the heuristics and comparing the performance of the resulting algorithms.