■ Solving 15-puzzle with A* heuristic search and pattern databases

Who hasn't come across the 15-piece sliding puzzle as a kid? The idea is to slide little square tiles in a frame with a single hole, until the numbers are in order. Computer algorithms can solve such puzzles using brute force enumeration. Starting with any board arrangement, you make all possible moves (up to 4 in this game) that lead to 4 new board states, then do all moves in each of the new states, and so on, until by chance we hit on the solution. The search graph grows exponentially as you can imagine, so this blind search technique will only work in games with small state spaces, like missionaries and cannibals (crossing a river), or the 8-puzzle (see pic). However the full 15-puzzle (4x4 tile board) has 16! (factorial = 2.1E13 trillion) states, so exhaustive enumeration is impossible.

Instead of blindly exploring all board states, heuristic search algorithms like A star use a cost estimate (number of tile moves in this case) towards the goal (solution) to guide the search, which is found much quicker. How do we know how many moves are left to solve a board? We don't, but we can guess the minimum cost if we consider each tile on its own and ignore the rest; it's like we cheat and remove a tile and put it in its goal spot. This is an admissible heuristic (manhattan distance) that will take us to the optimal solution.

Manhattan distance is a good heuristic for 15-puzzle, but we can do better. If the cost estimate of a state is closer to its actual value, then we'll find the solution quicker. Pattern databases offer a better estimate for the number of moves left to the goal. We concentrate on a small part of it, say tiles 1, 2 and 3 (the "pattern") and calculate the exact number of moves to bring these 3 tiles to their goal positions, from all possible arrangements of these 3 tiles. This will require an exhaustive enumeration as well, but now we only need to do 3 tiles out of the 15, and the problem is tractable ( 16!/(16-3)! = 3360 alternatives only). Once we finish the preparatory work and store these costs in a database, then during the A* solution, we look up the current location of tiles 1, 2 and 3 and read their exact precalculated cost.

We have to break up the entire board into sections and do a database for each set of tiles, then add up the cost of each sub-pattern to get the cost estimate of the whole board

To create the cost database for a pattern, we start with the goal (solved) state, and replace all tiles that aren't in the pattern with "don't care" wildcards. Then we do a breadth-first (BFS) exhaustive enumeration of alternative boards backwards, considering just our pattern and the hole. Whenever we move one of the pattern tiles, we add 1 to the cost, otherwise the cost stays unchanged — this ensures that the entire heuristic cost is additive. For illustration let's consider a tiny 2x2 board and focus on the possible locations of tile #1 and the hole:

The reason why the exhaustive BFS enumeration for a pattern is tractable is the existence of many equivalent duplicate states, which we ignore

As seen above the cost database for tile #1 has only 12 possibilities, and if we ignore the location of the hole, the possibilities drop to 4. This doesn't sound like a big improvement here, where the entire solution space has 4! = 24 states, but it makes sense for the 15-puzzle.

The idea of pattern databases isn't new, so wherever you read about it many things are taken as self-evident, but I had many open questions in my mind, e.g. how do you break up the tiles in groups? Does the segmentation shape play any role, or is it just the number of tiles in each group that matters? Clearly a larger pattern with more tiles will be a more accurate estimate of the cost-to-solution, but there is a trade-off: a 6-tile pattern has 5,765,760 alternative positions (10 times as much during BFS enumeration), so both the database size and solution time increase. Only one way to figure things out, experiment with the solution!

My un-optimized code couldn't deal with the 2GB memory required to solve the 6-tile pattern database, so I limit my investigations to 5-tile databases.

Figure 1. A few ways to dissect 15-puzzle into pattern segments

Here is the numerical experiment: solve a randomly created 15-puzzle that needs 52 moves for its solution, first using plain A* (without pattern databases), then create various databases and see the gain in solution speed, and whether the segmentation shape matters or not. I tried 2 different ways of breaking up the board in chunks of 5 pieces (3 databases), and one with 4 chunks (4-4-4-3 tiles, see the boards above). Here are the results:

I don't offer the C++ source code for download because it's messy, but if you want it send me an email

Pattern	Solution time	States expanded (total IDA*)	Database creation time	Database size
None	118 sec	82,908,832	—	0
5-5-5 (a)	0.19 sec	55,216	399 sec	9 MB
5-5-5 (b)	0.35 sec	106,046	390 sec	9 MB
5-5-5 (c)*	3.22 sec	945,586	395 sec	9 MB
4-4-4-3	2.5 sec	651,849	10 sec	0.8 MB

Table 1. Sample 15-puzzle solution times for various pattern databases

It is clear that spending some time to create the pattern database upfront (this is only done once and then reused) really pays! The basic iterative deepening A* (IDA*) search takes nearly 2 minutes to solve, but using a 5-5-5 triple database brings this down to under 1 second! If you examine table 1 above, the better heuristic cost estimates result in fewer nodes examined and less CPU time (1000x improvement!). Looking up solutions in the pattern database takes some time, but overall we are much better off.

The grouping of tiles also affects the solution speed, as you can see by the different 5-5-5 arrangements, one solves in 0.19, one in 0.35 and one(*) in 3.22 seconds! For the latter bad one I groupped tiles randomly, meaning that groups didn't have all tiles side by side. I don't understand why it matters that much, but obviously it does. The 0.16 second difference between the 2 "good" pattern arrangements (a-b) could be down to the particular puzzle solved. Perhaps a different starting puzzle would favor arrangement (b)? Who knows? Proving optimal groupings in discrete mathematics is way above my capabilities and patience <g>

Finally using 4 smaller pre-solved patterns (4-4-4-3 tiles) is better than nothing but an order of magnitude worse than 5-5-5 groupings. In pattern databases, as in many things in life, no pain no gain.

That's my curiosity satisfied for this kind of puzzle. I hope I also helped somebody out there grow their understanding solving these kinds of puzzles. Next stop, an algorithm for solving Rubic's cube?