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.
Answer
Improve This Solution
View Answer