Tower Of Hanoi

The Tower of Hanoi (also called The problem of Benares Temple or Tower of Brahma or Luca'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:
1.Only one disk may be moved at a time.
2.Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
3.No disk may be placed on top of a disk that is smaller than it.

The minimal number of moves required to solve a Tower of Hanoi puzzle is 2^n - 1, where n is the number of disks.

Origin :

The puzzle was invented by the French mathematician Édouard Lucas, first presented in 1883 as a game discovered by
"N. Claus (de Siam)" , and later published as a booklet in 1889 and in a posthumously-published volume of Lucas' 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 sixty-four 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 regarding the ancient and mystical nature of the puzzle popped up almost immediately.

If the legend were true, and if the priests were able to move disks at a rate of one per second, using the smallest number of moves, it would take them 2^64 − 1 seconds or roughly 585 billion years to finish, which is about 42 times the estimated current age of the universe.

There are many variations on this legend. For instance, in some tellings, 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.

Édouard Lucas

Solution :

Solution for: