A C++ implementation to solve the classic 8-puzzle game using
- The standard A* algorithm using Tile Mismatch Count and Manhattan Distance heuristics.
- A modified version of A* in which a node is expanded to a given fixed depth using BFS strategy. After expansion, nodes are added in the usual A* order.
Both implementations are compared on the basis of max. fringe length and no. of expanded nodes.
Option 1: Run the shell script 8Puzzle.sh
./8Puzzle.sh
Option 2: Open Terminal and issue following commands:
g++ 8Puzzle.cpp -o 8Puzzle
./8Puzzle
While generating random initial states, some states generated are invalid. They are not solvable. To generate a random set of valid initial states, uncomment lines 253, 254, 257, 258 and comment lines 260-262 (Given in Comments) in the file 8Puzzle.cpp.