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 Mastermind and 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.