This application finds the optimal solution to solve a 8 or 15-puzzle. By optimal solution, we mean a solution requiring the minimum numbers of moves.
Different algorithms are implemented : Breadth First Search, A* or Iterative Deepening A* (IDA*). You can use and compare these algorithms only for the 8-puzzle. Indeed, only IDA* are able to resolve a 15-puzzle relatively fast and without consuming too much memory.
A* and IDA* algorithms use heuristic function to find the optimal solution. Three heuristic functions are proposed : Manhattan Distance, Linear Conflict and Database Pattern.
This web application is deployed on Google App Engine infrastructure (Frontend Instance Class F2 : 1200MHz, 256 MB). The algorithm has 60 seconds to solve the puzzle.
The code is open-sourced and can be found here
If you want to have more details about how I've implemented this web application, please read the following post
|# of moves:|