Tower of Hanoi

Tower of Hanoi ~ An Interesting Classic Puzzle

Tower of Hanoi is an interesting classic mathematical puzzle. The Tower of Hanoi consists of three pegs and number of disks in different sizes. Though the number of discs can vary there should be only three pegs. In one of the pegs the disks are stacked in an ascending order with smallest disk at the top and the largest disk at the bottom.

Object of Tower of Hanoi:

The object of the game is to move all the disks from the left peg to the right peg. The moved order of the disk must be in the original order.

Rules to follow while playing Tower of Hanoi:

(1) Only one disk should be moved at a time.
(2) Never stack a larger disc on top of a smaller disk.


Note: The middle peg can be used as a temporary storage.

How to solve Tower of Hanoi:

1)Move the top N-1 disks from Source to Auxiliary tower,
2)Move the Nth disk from Source to Destination tower,
3)Move the N-1 disks from Auxiliary tower to Destination tower.
Transfering the top N-1 disks from Source to Auxiliary tower can again be thought as a fresh problem and can be solve in the same manner. So once you master solving Tower of Hanoi with three disks, you can solve it with any number of disks with the above algorithm.

Inventor of Tower of Hanoi:

François Édouard Anatole Lucas (1842 - 1891) invented the Tower of Hanoi puzzle. He was a famous French mathematician.


Lucas is known for his study of the Fibonacci sequence. He gave a formula for finding the nth term of the Fibonacci sequence. The Lucas sequence is named after him.


The Lucas sequence,
2, 1, 3, 4, 7, 11, 18,
The 3rd term is the sum of 1st and 2nd number.


The Tower of Hanoi puzzle was marketed in 1883 under the nickname N. Claus de Siam, an anagram of Lucas d'Amiens.

Legends related to Tower of Hanoi:

There are two similar legends related to Tower of Hanoi.


(1) According to a legend there is a Buddhist monastery at Hanoi. In the monastery there is a large room inside the room there are three posts with 21 golden disks. The ancient prophecy says the monks have to move only one disk per day. And after they have finished moving the last disk the earth will end!


(2) According to an old Indian legend, in the city of Benares there is a temple. There a brass plate is found with three diamond needles and 64 disks made of gold called the Tower of Brahma. The work of the Brahmins is to transfer the disk from one needle to another. The smaller disk should be placed on the top of a larger disk. When the have finished the tack the world will come to an end.