The 8-puzzle consists of an area divided into a grid, 3 by 3 for the 8-puzzle. On each grid square is a tile, expect for one square which remains empty. Thus, there are eight tiles in the 8-puzzle . A tile that is next to the empty grid square can be moved into the empty space, leaving its previous position empty in turn. Tiles are numbered, 1 through 8 for the 8-puzzle, so that each tile can be uniquely identified. The aim of the puzzle is to achieve a given configuration of tiles from a given (different) configuration by sliding the individual tiles around the grid as described above.1
In this repo I'll be finding solution for 8 Puzzle Problem using A* algorithm using Manhattan distance. To build the state space tree I'll be using pydot which is a Python wrapper for graphviz.
pydot==1.4.1
Graphviz Binary Download graphviz https://www.graphviz.org/download/
- Download graphviz binary
- Open solve.py and update the directory to point graphviz bin directory
# Set it to bin folder of graphviz
os.environ["PATH"] += os.pathsep + 'C:/Program Files (x86)/Graphviz2.38/bin/'
- Install all the requirements
pip install -r requirements.txt
python main.py
The state space tree is saved as "out.png".
