15 Puzzle: Technical stuff
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.
| "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
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:
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:
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.
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):
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:
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.