I implemented:
- Breadth First Search
- Depth First Search
- A* search algorithm
The solver uses A* search to find the shortest path to the goal in minimum time. To assign a heuristic value to a Node I used the Manhattan distance of that Node from the goal plus the path cost from the starting state to that Node.
The program requires python 3.5 and is currenctly compatible with Unix systems and Bash on windows 10 For simplicity the installation and download instructions will use the Debian (and derivatives like Ubuntu) package manager "aptitute" (apt-get) but feel free to replace it with your distribution's package manager. The following lines should install python3.5 on your computer, but results may vary depending on your distribution, do some research before executing.
sudo add-apt-repository ppa:fkrull/deadsnakes
sudo apt-get update
sudo apt-get install python3.5
Next we will install the python3 package manager "pip3" and then the modules needed for the program to work
sudo apt-get install python3-pip
sudo pip3 install asciimatics pyfiglet resource
There 2 ways to download the repository (at least as far as I know).
If you are unsure if you have the git module you can install it with
sudo apt-get install git
In order to download the repository you need to
git clone https://github.com/spirosbax/8_puzzle.git
this will create a directory called "8_puzzle" containing the repository files, then do
cd 8_puzzle
To change directory. Then run the file "driver_3.py" with
python3 driver_3.py
Go to the top right of the repository and click the download.zip button, then extract the containing folder and "cd" into it, lastly run the file with
python3 driver_3.py
I am open to suggestions for improving the A* algorithm, feel free to contribute. Want to contribute? Great! Fork the repository and start coding