Tower of Hanoi

The Tower of Hanoi (also called The problem of Benares Temple, Tower of Brahma or Lucas's Tower, and sometimes pluralized as Towers, or simply pyramid puzzle) is a mathematical game or puzzle consisting of three rods and a number of disks of various diameters, which can slide onto any rod. The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a conical shape. The objective of the puzzle is to move the entire stack to one of the other rods, obeying the following rules:

With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2ⁿ − 1, where n is the number of disks.

The puzzle was invented by the French mathematician Édouard Lucas, first presented in 1883 as a game discovered by "N. Claus (de Siam)" (an anagram of "Lucas d'Amiens"), and later published as a booklet in 1889 and in a posthumously-published volume of Lucas's Récréations mathématiques. Accompanying the game was an instruction booklet, describing the game's purported origins in Tonkin, and claiming that according to legend, Brahmins at a temple in Benares have been carrying out the movement of the "Sacred Tower of Brahma", consisting of 64 golden disks, according to the same rules as in the game, and that the completion of the tower would lead to the end of the world. Numerous variations on this legend exist, regarding the ancient and mystical nature of the puzzle.

At a rate of one move per second, the minimum amount of time it would take to complete the 64 disks would be 2⁶⁴ − 1 seconds or 585 billion years, roughly 42 times the estimated current age of the universe.

There are many variations on this legend. For instance, in some back stories, the temple is a monastery, and the priests are monks. The temple or monastery may be in various locales including Hanoi, and may be associated with any religion. In some versions, other elements are introduced, such as the fact that the tower was created at the beginning of the world, or that the priests or monks may make only one move per day.

The puzzle can be played with any number of disks, although many toy versions have around 7 to 9 of them. The minimum number of moves required to solve a Tower of Hanoi puzzle with n disks is 2ⁿ − 1.

A simple solution for the toy puzzle is to alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it to the next position in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd). If there is no tower position in the chosen direction, move the piece to the opposite end, but then continue to move in the correct direction. For example, if you started with three pieces, you would move the smallest piece to the opposite end, then continue in the left direction after that. When the turn is to move the non-smallest piece, there is only one legal move. Doing this will complete the puzzle in the fewest moves.

The iterative solution is equivalent to repeated execution of the following sequence of steps until the goal has been achieved: