Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Tower of Hanoi
Main Page | See live article | Alphabetical index

Tower of Hanoi

 

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 object of the game is to move the entire stack to another peg, obeying the following rules:

Table of contents
1 Origins
2 How to solve it
3 Applications
4 External Links

Origins

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 264 - 1 or roughly 1.8×1019 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.

In the classic science fiction story "Now Inhale", by Eric Frank Russel (Astounding Science Fiction April 1939, and in various anthologies), the human hero is a prisoner on a planet where local custom is to make the prisoner play a game until it is won or lost, and then execution is immediate. The hero is told, the game can be one of your own species, so long as it can be played in your cell with simple apparatus, strictly according to rules you write down before play begins and cannot change after play starts, and has a finite endpoint. The game and execution are televised planet-wide, and watching the desperate prisoner try to spin the game out as long as possible is a very popular entertainment; the record is sixteen days. The hero knows a rescue ship might take a year or more to arrive, so chooses to play Towers of Hanoi with 64 disks until rescue arrives. When the locals realize they've been had, they are angry, but under their own rules there is nothing they can do about it. They do change the rules that will apply to any future prisoners.

How to solve it

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

Recursive Algorithm

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

The above is a recursive algorithm: to carry out steps 1 and 3, apply the same algorithm again for n-1. 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.

Explanation of the Algorithm

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

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

Each time you re-build the tower from disc i up to 1, move disc i+1 from peg A, the starting stack, and move the working tower again.

Practical Algorithm

Alternately move disc 1 and one of the larger discs. If two of the larger discs are available, always move the smaller one onto the larger. When you move an odd-numbered disc, always move it one peg clockwise; when you move an even-numbered disc, always move it one peg counterclockwise.

An even easier way to remember this solution is to notice that the smallest disk gets every second move, and always moves in the same direction. In between smallest disk moves, there is only one legal move that does does not involve moving the smallest disk again.

In spite of the simplicity of the algorithms, the shortest way to solve the problem with n discs takes 2n-1 moves. It is not known in general how many moves are required to solve the puzzle when there are more than 3 pegs, although it should take no more than 2n-1 moves. (For somewhat intuitive reasons: the 3-peg solution can be used for more-than-three-peg games if one merely "ignores" the other 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 M-x hanoi.

Applications

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

External Links