How to solve the famous 15 sliding-tile puzzle

I've recently followed the artificial intelligence class given by and Sebastian Thrun . It was time for me to get my hands dirty and implement some algorithms seen in the class.
I've decided first to investigate the search algorithms i.e. Breadth First Search (BFS), Depth First search (DFS), A*... The idea is to build a web application able to quickly solve a shuffle puzzle with fifteen tiles.
This web application should be written in Java (using GWT for the client part) and be deployed in Google App Engine (GAE). This last requirement imposes that the algorithm has to find the solution of the puzzle in a maximum of 60 sec and doesn't need more than 256 Mb of memory (I configured the application to run on Frontend Instance Class F2 : 1200MHz, 256 MB).

If you don't want to read more, here is the result : http://n-puzzle-solver.appspot.com

The 8-puzzle
The 3x3 eight puzzle is easy to solve. The size of its state space is 9!/2 = 181,400 and the optimal solutions are up to 31 moves. In these conditions, even the BFS algorithm can quickly solve the puzzle. The A* using the Manathan Distance (sum of the distance betwen the current and the goal position for each tile) as heuristic function finds the solution in a few milliseconds.

The 15-puzzle
With its 10,461,394,944,000 (16!/2) different states and optimal solutions of up to 80 moves, the 4x4 fifteen puzzle is another story... The A* algorithm stores every generated nodes by keeping the list of visited nodes and the list of nodes to expand and it consumes quickly all available memory. It is so not able to solve most of the problems...

The Iterative Deepening A*
And what ?? Is it not possible to solve a 15-puzzle by using a path finding algorithm ? Fortunately yes it is ! After some research on Google, I found the algorithm to use : Iterative Deepening A* or IDA*. This algorithm was not shown during the class but we've learned its main component : Depth-First-Search. IDA* performs a series of depth-first search pruning a path when the cost f(n)= g(n) + h(n) (g(n) is the length of the path from the start to n and h(n) is a heuristic estimate of the length of the path from n the the goal state) of the last node exceeds a treshold. The treshold is set initially heuristic evaluation of the start node and increases to the lowest cost of all nodes pruned in the last iteration until a goal node is expanded.

IDA* being the linear-space version of A*, it resolves all instances of fifteen puzzles in respect of the memory constraint we have set. But what about the time constraint? The algorithm should be able to find the optimal path within 60 seconds. But sometimes when the puzzle is too complex (needs more than 60 moves to be resolved), this time limit is reached without the problem being resolved. A way to make the algorithm faster is to improve the used heuristic function i.e. make it more accurate.
The first significant improvement to Manhattan distance is the linear-conflict heuristic. A linear conflict exists when two tiles are in their goal row or goal column but they are in inverse order. Ex: if the first row is (2, 1, 3, 4), 2 and 1 are in linear conflict, one of these two tiles has to move down to allow the other to pass by and then back up. So two moves can be added to the Manhattan Distance.

The pattern database (PDB) are admissible heuristic functions implemented as lookup tables that store the lengths of optimal solutions for subproblem instances. (Compressed Pattern Databases, A. Felner, R. Korf, Journal of Artificial Intelligence Research 30 (2007) 213-247)

The pattern database heuristic consists in splitting the set of tiles into disjoint groups (2 or 3 groups for the 15 puzzle problem) such that every tile is being part of a group and no tiles belong to more than one groups. For all different configurations of the tiles in each group, we solve the problem optimally and store the solution (number of moves) in a table. From an implementation point of view, the pattern database is precomputed with a single breadth-first search backwards from the goal state counting only moves that are made by tiles in the considered group. For each new generated partial state (partial because we take into account only the positions of the tiles of the pattern), we store the number of moves needed to arrive at this state in an array. The index in this array is computed with this partial state.

During the search, the evaluation of the heuristic consists in computing an index for each pattern, getting the values from the tables and summing them.The most simple example of database pattern is the manhattan distance where each pattern contains only one tile.

In the context of my web application, I decide to use a 6-6-3 partitionning because it is the best ratio between performance and the amount of memory required to hold the database. Indeed, the pattern database have to be stored in memory and in the case of 6-6-3, the tables consume +/- 34MB.

With the additive pattern database, the IDA* solves most of the 15 puzzle configuration in a few seconds !

The code
The code is open source and is available in google code: http://code.google.com/p/julien-labs/source/browse/#svn%2Ftrunk%2FSlidingPuzzle%2Fsrc%2Fbe%2Fdramaix%2Fai%2Fslidingpuzzle
Implementation of the different algorithms can be found in this package: http://code.google.com/p/julien-labs/source/browse/#svn%2Ftrunk%2FSlidingPuzzle%2Fsrc%2Fbe%2Fdramaix%2Fai%2Fslidingpuzzle%2Fserver%2Fsearch
You can reuse the code as you want. You only have to adapt the State and Node object to fit your problem.

The web application : http://n-puzzle-solver.appspot.com

To conclude, it was very interesting to deepen the theory that we seen in the class. I hope still to find time to investigate other algorithm seen in class like... the particule filter for instance !!

Hashtags