The 8-tile puzzle is a well-known sliding puzzle. It contains 8 numbered tiles numbered 1-8, and an empty tile. In order to solve the puzzle, the tiles must be moved from a given starting position to a specified ending position, however, tiles can not "swap" places with each other. They may only move into the empty space.
Python 3 must be installed along with the Tkinter, Numpy, and matplotlib libraries. If you do not have the required Python libraries installed, run the following command:
pip3 install numpy matplotlib
For TKinter, refer to the following stack overflow page for OS-specific instructions
- Run
git clone [email protected]:dmogilevsky/A_star_Search.gitor copy the astar.py file onto your local machine. - In the directory you have saved the file, run
python3 astar.py
When the solver is started, a random game board will be initialized alongside an empty plot. The plot will graph the search space by plotting each board state onto the plot according to its heuristic (calculated distance from the solved state) and its distance from the starting position (calculated as the number of moves to get to this state). Additionally, the graph will show lines representing which board states each board state came from.
You can configure the solver in the following ways:
- Check Live Board/Graph Updates in order to see the board states/graph update as the solver searches through the solution space (Please note, this can significantly slow the speed of the solver)
- Change the delay time (measured in seconds) which will change the delay between each move shown in the solution once the solution is found
When a solution is found, the solver will go back to the board's starting position and move through the solution. The lines on the graph will be updated, showing the path of the solution.
Below is what the solver looks after solving and backtracing:
Additionally, a text file called output.txt will be created in the directory showing all of the board states explored