Assignment

This needs to be a C++ (or any other .net language) program that will implement a Breadth-First Search and a Depth-First Search to solve an 8-piece Slider Puzzle.

For this program, the above search strategies must be used to solve the 8-piece Slider Puzzle. The constraints of this program will be as they would be if the user were holding an actual, physical, version of the puzzle in their hand.

• A tile cannot be removed from the environment

• A tile cannot pass over or behind another tile

• A tile can only be moved up, down, left or right (no diagonal moves)

• A tile can only be moved into an empty space

The goal state of the puzzle should be:

1 2 3

4 5 6

7 8

This program will need a simple menu for the user interface. This menu should include options for the user to generate a puzzle (or choose a known good starting state of easy, medium, or hard difficulty. the puzzle generation is optional), run each of the searches against the generated puzzle, and an option to exit the program. The user interface should look something like this:

Welcome to the 8-piece Slider Solver

Please choose one of the following:

1. Generate a random puzzle

2. Run a Breadth First Search

3. Run a Depth First Search

4. Exit

Once a puzzle is generated, at least one of the searches must be run against it (the program should be able to do more than one per puzzle as well). The user should choose the search. So, once a puzzle has been generated, the main menu should be called again to allow to the user to choose which search to run.

After the user chooses a search, the program should output the results. The program should keep track of what search was used, what the starting state of the puzzle was, whether a solution was found (IF YOU ARE GENERATING RANDOM PUZZLES, SOME PUZZLES WILL HAVE NO SOLUTION! THE PROGRAM MUST BE ABLE TO IDENTIFY THIS AND OUTPUT THAT THE PROGRAM COULD FIND NO SOLUTION!), at what depth the solution was found, how many nodes were expanded to find the solution, and how long it took the program to find the solution. The program should then output the results of the search like so:

(Print Name of Search Used)

1. At what depth was the solution found?: (print depth)

2. How many nodes were expanded?: (print depth)

3. How long did the search take?: (print time)

4. Exit

Once the program has run a search against the generated puzzle, the program should return to the main menu so that the user can choose to generate a new puzzle, run another search on the puzzle that was already generated, or exit the program.