Tower of Hanoi

Tower of Hanoi Puzzle

Alternate Names

Tower of Brahma, End of the World Puzzle, Pyramid Puzzle, Pagoda Puzzle

No. of Players

Two

Equipment

All one really needs for this puzzle are several objects which become incrementally larger and can be stacked like a pyramid with the largest at bottom. Any set of objects will do, including coins and any flat surface will work for a playing board. Only three such objects are needed to play a very simple version, but you can play with as many stackable counters as desired. The more counters used, the more difficult the puzzle becomes. Five or six counters are sufficient for most players. Traditional marketed versions are composed of varying doughnut shaped objects which are skewered on vertical posts that fit through the doughnut’s hole.

History

In European tradition, it is claimed that this game/puzzle was invented by the French mathematician, Edouard Lucas, in 1883. In reality, however, the puzzle is probably much older as Lucas himself was inspired by a popular legend of a Hindu temple. The legend, told with varying details, says that a group of monks have been assigned to a large version of this puzzle with sixty-four discs by an ancient prophecy. According to the legend, when the last move of the puzzle is completed, the world will end.

Objective

The object is very simple: all one has to do is reform a stack of objects into another stack. There are only three positions where the objects may be stacked. Typically, the game begins with the counters stacked at the left side of the board and the puzzle is completed when they are all restacked at the right side position of the board, although which position is used for the start and finish is in fact arbitrary.

Play

The game begins with all counters in a neat stack at the leftmost position on the board. They are stacked with largest at the bottom of the stack, with the next largest on top of it and so on to the smallest at the top of the stack. A counter may be moved from the top of any stack to a vacant position or to the top of any other stack, so long as there is never a larger counter on top of a smaller one. Only one counter may be moved at a time.

Strategy

The minimum amount of movements to solve any tower of Hanoi puzzle that is composed of counters of an amount called n is

2^n – 1

Thus a puzzle of five counters can be solved in 2^5 – 1 = 32 – 1 = 31 moves. Thus, if our Hindu monks of prophecy are working on their puzzle of sixty-four discs and they are able to move about one disc per second, they should be able to complete the puzzle in about 585 billion years. We should be safe if they are not cheating.

Variations

As stated above, any number of incrementally sized objects can be used. Reve's Puzzle is a variation with four pegs that the counters can be placed on, instead of three.

Sources

1. Tower of Hanoi at Wolfram Mathworld. http://mathworld.wolfram.com/TowerofHanoi.html