The basic rules for the puzzle are as follows: You are given 3 poles and 'x' number of discs of various sizes (no two discs have the same size). The discs are placed in order from largest (which is on the bottom) to smallest (which is on the top). The point of the puzzle is to move all of the discs from the first pole to the third (although it could just as easily be the middle one, it doesn't actually matter) by following two rules. Firstly, you may move one (and only one) disc at a time. Secondly, you may never place a larger disc on top of a smaller one.
"The puzzle was invented by the French mathematician Edouard Lucas in 1883. There is a legend about an Indian temple which contains a large room with three time-worn posts in it surrounded by 64 golden disks. The priests of Brahma, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle. According to the legend, when the last move of the puzzle is completed, the world will end. The puzzle is therefore also known as the Tower of Brahma puzzle. It is not clear whether Lucas invented this legend or was inspired by it." Now, for the math behind this (and to put this into perspective for you), if the priests in this legend were really really dexterous and were able to move these giant discs so that a single move took only a single second, using the most concise number of moves (which this applet does, by the way) it would take almost 585 1/2 billion years to complete this task. That being said, the universe is estimated to currently only be about 13.7 billion years old right now.[1]
This program was actually an assignment for a Java class I took in college but I decided to expand upon it. To an individual who has never seen or heard of this puzzle before, thinking of the math behind it may seem to be rather complicated (as it did for me when I first heard of it) but realistically there is a simple equation that will tell you the number of moves required to complete the puzzle:
In this equation, D is the number of discs that you are solving for, meaning that the total number of moves is equal to 2 to the power of the number of discs, minus one. Algorithmically this is only marginally more complicated. (I could go into details in this, but the wikipedia article will probably do a better job of explaining it and it provides more types of algorithmic solutions than I really have bothered to understand anyway (just in case you want to know how to do it in binary).
In a programming sense, though, knowing the number of moves isn't really the biggest problem in solving this puzzle graphically. The bigger issue is really animating the soluting (this is especially true in java, which is what this applet is written in). While you can use one of the simple algorithms to figure out which move to take next, you then need to tell the algorithm to wait until the disc has visually moved all the way before letting the program figure out which disc to move next (and then moving it). I'm sure that for advanced programmers this isn't as much of an issue as it was for a class of beginners, but it was quite a lesson.
As a last note, and to put this in just a bit more perspective, remember when I mentioned that it would take 585.5 billion years to complete a puzzle with 64 discs and each disc took a single second to make a move? In the applet that I wrote, it takes well over a second to make a single move (in some cases over 2 seconds) meaning that if you ran this applet with 64 discs, it would take... well let's just say that you don't want to pay for the energy bill that would ensue... Anyway, this is part of the reason why I have a 16 disc limit on this applet. (Trust me, 16 discs will make you wait long enough!) The second reason why I chose this number is because using 13 or so discs with this applet is pretty much the max you can really do before you can't tell when some discs are larger than others.
