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

Several heuristics in the literature purport to improve on thissee, for example, Nilsson (1971), Mostow and Prieditis (1989), and Hansson et al. (1992).

1. Test these claims by implementing the heuristics and comparing the performance of the resulting algorithms.
2. Construct the search tree to represent the problem.
3. Write in C++ language to solve the 8-puzzle problem.
4. Submit your work (search tree, heuristics, code, running results)