[SOLVED] Implementing 8-puzzle search in java with full source code | download now

The 8-puzzle problem

In 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.

2. What you must do

2.1 Implementing 8-puzzle search

In 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:

2.2 Experimenting with Search Strategies

The search engine in the search4 folder implements the following search strategies:

• Breadth-first
• Depth-first
• Branch-and-Bound
• A*

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.
• Hamming distance, which is the number of tiles out of place.
• 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.

Get your project now 

Buy now