Most toy versions of the puzzle have 8 discs. The game seems impossible to the novice, yet is solvable with a simple algorithm:

To move n discs from peg A to peg B:
The above is a recursive algorithm: to carry out steps 1 and 3, apply the algorithm again for n1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n= 1. This step, moving a single disc from peg A to peg B is trivial.
A more humanreadable version of the same algorithm follows:
Each time you rebuild the tower from disc i up to 1, move disc i+1 from peg A, the starting stack, and move the working tower again.
Alternately move disc 1 and one of the larger discs. If two of two of the larger discs are available, always move the smaller one onto the larger. When you move an oddnumbered disc, always move it one peg clockwise; when you move an evennumbered disc, always move it one peg counterclockwise.
In spite of the simplicity of the algorithms, the shortest way to solve the problem with n discs takes 2^{n}1 moves. It is not known in general how many moves are required to solve the puzzle when there are more than 3 pegs.
The Tower of Hanoi is a problem often used to teach beginning programming. A pictorial version of this puzzle is programmed into the emacs editor, accessed by typing Mx hanoi.
The puzzle was invented by the French mathematician Edouard Lucas in 1883. There is a legend about a Hindu temple whose priests were constantly engaged in moving a set of 64 discs according to the rules of the Tower of Hanoi puzzle. According to the legend, the world would end when the priests finished their work. 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.
Two pages about the origins on the puzzle:
Search Encyclopedia

Featured Article
