The **Tower of Hanoi** (also called **Towers of Hanoi**) is a mathematical game or puzzle. It consists of three pegs, and a number of discs of different sizes which can slot onto any peg. The puzzle starts with the discs neatly stacked in order of size on one peg, smallest at the top, thus making a conical shape.

The towers of Hanoi (photo EvH)'' |

The object of the game is to move the entire stack to another peg, obeying the following rules:

- only one disc may be moved at a time
- a disc can only be placed onto a larger disc (it doesn't have to be the adjacent size, though: the smallest disc may sit directly on the largest disc)

Table of contents |

2 Explanation of the Algorithm 3 Practical Algorithm 4 Origins 5 Applications 6 External Link |

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

- label the pegs A, B, C -- these labels may move at different steps
- let
*n*be the total number of discs - number the discs from 1 (smallest, topmost) to
*n*(largest, bottommost)

To move n discs from peg A to peg B:

- move n-1 discs from A to C. This leaves disc #n alone on peg A
- move disc #n from A to B
- move n-1 discs from C to B so they sit on disc #n

A more human-readable version of the same algorithm follows:

You now have 2 discs stacked correctly on peg C, peg B is empty again- move disc 3 to peg B
- repeat the first 3 steps above to move 1 & 2 to sit on top of 3

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 M-x 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.

Interestingly, if the legend were true, and if the priests were able to move discs at a rate of 1 per second using the smallest number of moves, it would take the priests 2^{64} - 1 or roughly 1.8×10^{19} seconds to finish the puzzle. This is equivalent to about 580,000,000,000 years, which is more than the estimated age of the universe.

Two pages about the origins on the puzzle:

- http://hanoitower.mkolar.org/HThistory.html
- " class="external">http://www.lhs.berkeley.edu/Java/Tower/towerhistory.html

The Tower of Hanoi is frequently used in psychological research on problem solving. There do exist also variants of this task called Tower of London for neuropsychological diagnosis and treatment of executive functions.