The 8-puzzle problemIn this project you will implement a solution to the 8-puzzle by state-space search, using the search engine described in the lectures, and experiment with search strategies.
What you must do
Implementing 8-puzzle searchIn the search2 folder in the Java download on the COM1005/2007 MOLE site is the code for the simple search engine and for Jugs problems. Note that you may have to recompile the code for your version of Java.
• Following the instructions in section 2.9 of the lecture notes, write classes to implement a state-space search for 8-puzzle problems.
• You should not need to change the code for the search engine except perhaps to control how much it prints as a search proceeds, and to stop the search after a given number of iterations (in an 8-puzzle the search tree can become large).
• Test your implementation with breadth-first searches for the following initial con- figurations and the same goal state as above:
Experimenting with Search Strategies
The search engine in the search4 folder implements the following search strategies:
In this case we won’t consider Depth-first and Branch-and-Bound is the same as Breadth- first because we have uniform costs. We’ll compare Breadth-first with 2 variants of A*.
• Adapt your 8-puzzle classes for search4. This means that your 8-puzzle state must now include a local cost g (always 1 for the 8-puzzle), and an estimated remaining cost estRemCost, which is used by A* and must be an underestimate of the true cost.
• Code two alternative methods in your 8-puzzle state class for computing estRemCost, assuming that the target pattern is always the same, as above.
o Hamming distance, which is the number of tiles out of place.
o Manhattan distance, which is the sum of the moves each tile needs to make before it is in its correct position.
The experiment is to compare the efficiency of breadth-first, A*(Hamming) and A* (Manhattan) over a number of puzzles. You are testing the hypothesis that A* is more efficient than breath-first, and the efficiency gain is greater the more difficult the problem and the closer the estimates are to the true cost. CAUTION: 8-puzzle search trees can be surprisingly large. You may have to wait a long time for a search to conclude.