This project is meant to help me explore different search techniques used in artificial intelligence to solve a sliding 8 puzzle. The Sliding 8 puzzle is fully playable and it also incorporates the following 5 algorithms to automatically solve the puzzle:
- Breadth First Search (no closed list)
- Breadth First Search (with a closed list)
- Depth First Search
- A* Search (using Manhattan Distance heuristic)
- A* Search (using Straight Line Distance heuristic)
The puzzle starts out fully solved then the user may either manually enter moves to randomize the board or they can hit (1) and apply 100 random moves to the board. Once the board is fully randomized the user has a choice between the 5 individual algorithms listed above with the commands (5,6,7,8,9) or they can hit (0) to solve the board with each algorithm individually and report the results for comparison.
*Note: I limited the search to 3,000,000 nodes so that I would not run out of memory. This can easily be changed, if needed, by changing the value in the Solve() method of Solver.cpp.
This project is built using c++11
To compile just open bash in a linux terminal that has g++ installed, navagate to the folder that you cloned the project in and type the command:
make
Then to run the program type:
bin/runner
- Fork it!
- Create your feature branch:
git checkout -b my-new-feature - Commit your changes:
git commit -am 'Add some feature' - Push to the branch:
git push origin my-new-feature - Submit a pull request :D
Apache 2.0