15 Puzzle: Technical stuff

"Artificial intelligence (AI) is a process by which mechanical devices are able to perform tasks which, when they are performed by humans, require some thought."    Paul Y. Gloess, Understanding Artificial Intelligence, 1981

I'm not sure I would go so far as to call the solution algorithm of this game artificial intelligence. The irony of it is, the 15 puzzle doesn't take much intelligence at all to solve. It was after figuring this out that I knew I could make the applet self-solving. (I've seen it done with the full "decision-tree" artillery as well, but why bother?) And once you know how it works, it becomes pretty boring to play. A monkey could do it. One with a bit of discipline, anyway. I'll explain the technique here, so read no further if you want to keep the legendary 15 puzzle a challenge.

The "trick" is to break it up into smaller sub-problems that are trivial to solve, or become trivial to solve if you do them in the right order. We'll take it from a human perspective first. Start with getting the 1 and 2 into their proper places. 1 first, then 2. After you're done with that, you don't put 3 right next to them. You place it in the top right corner, and then the 4 right below, like this:

1	2		3
14	12	6	4
5	11	13	7
15	9	10	8

After placing the hole between the 2 and 3, you can then drag both 3 and 4 along into their proper positions. That takes care of the first row. The second one works exactly the same. 5 and 6 first, followed by 7 out on the right edge with the 8 just below it, and then you are halfway done.

The final two rows are easiest to solve if you work them through sideways, just like you did with the 3 and 4 and the 7 and 8 earlier. Place the 13 and 9 like this:

1	2	3	4
5	6	7	8
13	9	15	12
	14	11	10

Use the hole to drag them both along into their proper column. Then you do the same with the 14 and the 10. After that, you only have the bottom right 2x2 square left. You solve it by simply rotating the pieces, which is done by moving the hole around inside that square one or more full rotations. It doesn't matter which way.

1	2	3	4
5	6	7	8
9	10	12	15
13	14		11

This sounds a little too unproblematic -- and it is. Every now and then you won't be able to pull the drag-along trick off directly. We'll take the 3 and 4 as an example. Odds are that when you have put the 3 in the top right corner, the 4 happens to be in such an awkward place that you can't move it to the position below the 3 without moving the 3 (or the 2) as well. Like this, or something similar (I'm only showing the top right 2x3 pieces):

4	3
	9
12	15

But this is perfectly OK. You just need to send the 4 on a little detour down the left-hand side of this 2x3 group, and then up on the right-hand side, to dock with the 3. These are the steps:

3 4 9 12 15

3   4 9 12 15

3 9    15 4 12

3 9 15 12   4

3 9 12    15 4

3 12 9 15 4

12 3 9    15 4

12 3 9 4 15

You do the same thing if you run into trouble with the 7 and 8, the 9 and 13 or the 10 and 14, except that in the last two cases you have to think sideways, or lean your head 90 degrees to the left, whichever feels easier.

This description is of no real use to a computer yet, however. We need to break it up into even smaller sub-problems. Like how do you move a piece from its current position to a given destination without disturbing any of the pieces you have already aligned? How do you select a proper path? It turns out that, given the above order, you just have to move it sideways and then up. This will always work, with the exception of the "awkward" cases. They, on the other hand, are few enough to be handled mechanically using some kind of lookup table.

The next level of sub-problems is how to move the piece each step along a selected path. This is, of course, done by moving the hole to the next step position and then moving the piece into the hole. So how to you select a path for the hole? Well, to begin with, you should mark the already aligned pieces as "obstacles". Then you break this problem up one final time. First you select a path for the hole to one of the (up to) 8 neighboring positions of the target piece. Take one step at a time, horizontally or vertically, in whichever proper direction isn't blocked.

Once you are in a neighboring position, you know that the target place of the hole is just in another neighboring position. To get to it, pick either the clockwise or counter-clockwise path that is the shortest and/or not blocked by anything. Formulating an algorithm for this is rather easy. Check the source code on the ingredients page for details.