We gave two simple heuristics for the 8-puzzle: Manhattan distance and misplaced tiles. Several heuristics in the literature purport to improve on this—see, for example, Nilsson:1971, Mostow+Prieditis:1989, and Hansson+al:1992. Test these claims by implementing the heuristics and comparing the performance of the resulting algorithms.