15 Puzzle: History
In early December 1998 I got a message from a guy who presented a "challenge"
in the form of what he called a "cube", but what most people refer to as
the 15 puzzle. He was writing a program and wanted to know how to go from
an initial random configuration to the proper order.
That sort of thing happens to me a lot. Just because I've written
Rubik's Cube versions,
people think I'm some kind of genius who knows every aspect of programming
mind games (well, they're half right :-).
Whenever I'd played the 15 puzzle in the past I had been too impatient to
think of a long-term strategy. I had just shuffled the pieces around and
hoped for the best. But if kids can solve that puzzle, there has to be an
easy way to do it -- and if there's an easy way to do it, that should be
possible to formulate as an algorithm. I searched the web for auto-solving
15 puzzles, to see if I could find something to refer the guy to. (Ideally I
should have told him to stop bothering me and do his own research, but I
didn't have the heart.) There were a couple of such
applets out there, but none of them really useful. Instead of relying on a set
of rules, they were based on classic AI techniques of examining a wide
range of possible move combinations.
So I had to sit down and take a closer look at the 15 puzzle myself.
Fortunately it wasn't long before I noticed that the puzzle became quite
trivial if you just approaced it methodically. So I gave the guy some
brief instructions (I doubt they made much sense to him, but he
stopped writing), but after a while I started to feel it would be a shame to
let my little "discovery" go to waste and decided use the following weekend
to build a self-solving 15 puzzle of my own.
But I couldn't just give it a
run-of-the-mill design. (I mean, thousands of programmers have done
that already, so what would be the point?) And just forget about having the
pieces form some cute picture. Tetris aside, there is no more
over-used web programming concept in the universe. The only gimmick left,
ironically, seemed to be to give it the exact look and feel of the original.