The solver for the famous 8-puzzle problem using A* Search and Manhattan distance heiristics. The solver takes in the input puzzle and return a solved output.
Salient features of the code are :-
- A* search with iterative deepening implemented using the Manhattan distance heuristics.
- Repeat of searched states were avoided by keeping track of the visited states using a boolean vector.
- A state was represented using two parameters - The present state of the puzzle and number of moves needed to reach that state.
- A priority queue with priority based on Manhattan Distance heuristics was implemented using the STL containers.
- The feasibility for the solution of the puzzle was checked using equivalence classes with respect to reachablity. This proves to be a critical optimization in the early stage of the code.
Repository contents :
- A c++ code to solve an 8 puzzle
- A sample input to check the code against testcases
- The corresponding output for the given input.