Solving Sliding Block Puzzle using BFS, A* & Pattern Database Heuristic.
- Built a Sliding Block Puzzle Environment and used BFS and A* Searches to find the best possible answer.
- Designed a Patten Heuristic database with an unending BFS search that began at the objective and proceeded to all of the states that could be reached from there.
- Obtained 1.28x & 937x speedups using A* with Manhattan Distance & Pattern Database Heuristics (where 1x is the speed of BFS).
- Sliding_Block_BFS.py - BFS Algorithm
- Sliding_Block_AStar.py - A* Algorithm using Manhattan Distance
- Sliding_Block_AStar_DBS.py - A* Algorthm with Pattern Database Heuristic
- Pattern_Database_3x3.py & Pattern_Database_3x3.py - Files used to generate the Pattern Databases
- The remaning files are the Pattern Databases and the test cases
Note: The Algorithms, Outputs & Performances of the programs can be found in the Report.pdf file.