mahdavipanah / pynpuzzle

pynpuzzle is an application that helps you to solve n-puzzle problem and also to test your algorithms for n-puzzle problem. It is written in Python and uses tkinter for it's graphical interface.

NOTE: This project is not actively maintained and you may encounter some issues running it. One known issue is due to the psutil library's access denied issue on macOS. Feel free to send a pull request at anytime.

Installing

Prerequisites

• Python3.5+
• tkinter
• psutil

Debian Linux (Ubuntu)

Open terminal and install these packages:

sudo apt-get install python3.5 python3-tk python3-psutil

Now you can run pynpuzzle from terminal: ./pynpuzzle

Windows

Download and install Python's installer (version 3.5 or higher) from it's official website. After installing python, open command line and install psutil package using pip: pip install psutil. Now you can run pynpuzzle.py from command line: python pynpuzzle.py.

Adding new algorithm

pynpuzzle loads algorithms from algorithms folder next to pynpuzzle.py.
All python files (.py) inside this folder (./algorithms/*.py) are considered as algorithms and pynpuzzle tries to load them.
An algorithm module should have a search function that accepts two arguments.
First argument is the n-puzzle's current state and the second one is the goal state.
Each of the arguments are two dimensional lists that represnt a n-puzzle. For example (test_algorithm.py):

def search(state, goal_state):
  """
  Test algorithm
  """
  pass

Docstring of the function will be presented as the name of the algorithm in app's algorithms combobox (if function has no docstring, module's filename will be used. test_algorithm in this case.).
And finally, function should return an m*n*n three dimensional list which represents a set of paths from state to goal_state.

Logs about algorithm's modules can be seen from menubar's Show logs item.

These algorithms are included in the app and can be used as code examples for adding new and more complex algorithms:

• A* tree search algorithm using manhattan distance heuristic
• A* tree search algorithm using misplaced tiles heuristic
• Breadth-first search algorithm
• Iterative deepening depth-first search algorithm
• Uniform-cost search algorithm

Author

Hamidreza Mahdavipanah

License

MIT