This python file solves 8 Puzzle using A* Search.
Current Status: Currently, the solver prints all the possible steps it has explored leading to the answer. I am currently looking for a way to print only those steps that are relevant to the answer. Let me know if you have anything in mind.
To run, use the following notation in command prompt:
python Puzzle8Solver.py <heuristicChoice> <1 to 8 in any order with a _ in middle>
Example:
python Puzzle8Solver.py 1 1 4 2 6 3 5 _ 7 8
Heuristic [Source]
The code currently uses Manhattan Distance as the heuristic function. The Manhattan distance heuristic is used for its simplicity and also because it is actually a pretty good underestimate (aka a lower bound) on the number of moves required to bring a given board to the solution board. We simply compute the sum of the distances of each tile from where it belongs, completely ignoring all the other tiles. For example, the Manhattan distance between the current state and goal state is 7:
| Current State | Goal State | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
Distance:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| 0 | 2 | 3 | 0 | 2 | 0 | 0 | 0 |
0+2+3+0+2+0+0+0 = 7
This is so, because the tile "1" is 0 move away, the tile "2" is 2 moves away, the tile "3" is 3 moves away, the tile "4" is 0 move away, the tile "5" is 2 moves away, the "6" tile is 0 move away, the "7" is 0 move away, and the "8" is 0 move away.