Reference no: EM132841976

The 8-Puzzle: Search Algorithms

Instructions

• Your task is to write a C++ program that will solve the 8-puzzle problem using a selection of search algorithms, and their variants.

• The successors of a state are to be generated in a FIXED order, namely move the blank tile: Up, Right, Down, then Left.

Words of caution: Note that if you are using a stack data structure (last in, first out) as a container for the Search Nodes, then you will have to push into the stack the Left successor first, followed by the Down, Right, then Up successors so that the Up successor would be the first to be popped out of the stack.

• An AnimateSolution() function has been provided that you can use to animate the sequence of moves (i.e. path) calculated by the algorithms. A start-up program (compiles with gcc 9.2) with a graphics library and 2 batch files for generating experiment results are available for downloading from stream.

• It is up to you to write any functions, classes or data structures that you may require. However, for each of the algorithm, there is a specific minimum STL data structure that is required. You can use cout statements to trace the algorithms' execution.

• For each implementation of the algorithms below, include codes that will capture the following information during the algorithm's execution.

a. Max. Q length - e.g. 26
b. Path length - the number of moves to solve the puzzle, e.g. 30
c. Number of state expansions - e.g. 157
d. Actual running time in seconds (use the clock() function as shown in the start-up codes)

• Write your algorithm implementations inside the skeleton functions provided for the required algorithms. Do not change the names and input parameters of these skeleton functions as the batch files would refer to them. Each algorithm implementation should return the sequence of moves as a string. Moreover, make sure that your program runs with the supplied batch files for generating the tabulated experiment results. Your assignments will be marked using them.

e.g. string progressiveDeepeningSearch_NonStrict_VisitedList(string const initialState, string const goalState, int &numOfStateExpansions, int& maxQLength, float &actualRunningTime, int ultimateMaxDepth);
o Note that the function uses pass by reference to copy the statistical results back to the calling function

Part 1: Progressive Deepening Search (PDS)
• Use the following Search Node pushing sequence (for a Stack data structure): Left, Up,

Right, Down. Effectively, search nodes will be popped out in the following order: Up, Right, Down, Left.

a) PDS with the Visited List - in your implementation, add a facility that checks and avoids local loops
b) PDS with the Non-Strict Visited List

Part 2: Uniform Cost Search
• Use the following search node pushing sequence (for a Heap data structure): Down, Right, Up, Left
• Implement the Q container using the heap data structure implementation - available in the C++ Standard Template Library (STL): use make_heap(), push_heap(), pop_heap(), etc.

a) Without the Strict Expanded List
b) Using the Strict Expanded List

Part 3: A* Search with the Strict Expanded List
• Use the following search node pushing sequence (for a Heap data structure): Down, Right, Up, Left
• Implement the Q container using the heap data structure implementation - available in the C++ Standard Template Library (STL): use make_heap(), push_heap(), pop_heap(), etc.

c) Using the Misplaced Tiles heuristic
d) Using the Sum of Manhattan Distance heuristic

Part 4: Experiments
Test your implementation of the different algorithms by performing experiments using the 5 given (start, goal) state combinations below. Run your program until it either returns a solution, the Q becomes empty (no solution), the computer runs out of memory, or until the program crashes. Use the batch files provided to run all the experiments and collect the results easily.

Tabulate the experiment results in an Excel worksheet (convert the output of the batch file into a worksheet). Please check if the format of your tabulation of results matches the template provided (see template.xlsx). Use your surname_forename.xlsx as the name of your Excel file, and assign the name "results" to the sheet name containing the experiment results. For a group submission, just use one of the member's name.

If there is no solution found for a given (start, goal states), simply leave that section blank in the table, or write 0 in each of the required statistical measure (e.g. path length, no. of state expansions, max q length, running time, etc.).

Specify under the "comments" section of the tabulation of results if any of the following was observed for a given (start, goal state) combination:
• the program ran out of memory
• program crashed without any warning
• the Q turned empty; thus, allowing the program to close properly

BONUS
» 1 Bonus mark will be given to an original implementation and correct usage of a hash function, to speed up search. The hash value returned must be of numeric type, and there should be an

evidence of search speed increase.

(Start, Goal) State Combinations
Note: 0 - blank space

GOAL STATE: ((1 2 3)
(4 5 6)
(7 8 0))

Run the different algorithms on the following START STATES: 1. 608435127
2. 743286051
3. 647850321
4. 185024367
5. 867254301

Hints:
You can step through the search by including a getch() function (made available via the graphics engine provided in the start-up codes) inside your main loop to pause the program until the user presses any key.

Attachment:- Search Algorithms.rar