Assignment
Write a C++ (or any other .net language) program that will implement a Breadth-First Search, a Depth-First Search, and an A* Search (using the number of misplaced tiles) 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 project 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, 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:
Generate a random puzzle
Run a Breadth First Search
Run a Depth First Search
Run an A* Search
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 sewrch per puzzle as well, however, this is not completely necessary). 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 (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)
Staring State: (print starting state of the puzzle here)
Was a Solution found?: (print yes or no)
At what depth was the solution found?: (print depth)
How many nodes were expanded?: (print depth)
How long did the search take?: (print time)
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.
This program will need functions to accomplish the following (not all of these functions are necessary. Two or more can be combined into a single function. Some can be omitted entirely. These are just examples):
A function to create an interface menu for the user
A function to generate a randomized 8-piece puzzle and store it for use
A function to run a Breadth-First search
A function to run a Depth-First search
A function to run an A* search
A function to return the user to the menu after puzzle generation, error, or after running a search
A function to print the results of a search to the user (starting state, if a solution was found, depth of solution, how many nodes were expanded, time taken to finish)
A function to exit the program.