Towers Of Hanoi

The Towers of Hanoi puzzle was published in 1883 by French mathematician Edouard Lucas, under the pen-name N. Lucas de Siam. The Towers of Hanoi puzzle basically consists of three towers. A specific number of discs are placed on one of the towers, such that the discs are placed in the ascending order of their size from top to bottom. The objective of the game is to move the discs to another tower such that they still follow the same order. Further only one disc can be moved at a time and a bigger disc cannot stand on a smaller disc.

Consider the following scenario. Here we have three towers. The first one will have three discs arranged in ascending order from top to bottom. The other two towers will be empty. The ending scenario could be - The towers 1 and 2 will be empty and the third one will have the three discs arranged in ascending order from top to bottom. The challenge of Tower of Hanoi is to achieve this with the constraint that only one disc can be moved at a time and a bigger disc cannot stand on a smaller disc. The choice of starting tower and destination tower is possible and also the number of discs can be chosen. The more the number of discs, the challenge becomes more difficult.

Legends

There is a legend related with the game which states that in Benares, during the reign of the Emperor Fo Hi, there was a temple with a dome which marked the center of the world. In this temple there contained a large room with three time-worn posts in it surrounded by 64 golden discs. The priests of Brahma, acting out the command of an ancient prophecy, have been moving these discs, in accordance with the rules of the puzzle. According to the legend, when the last move of the puzzle is completed the world will end. The puzzle is therefore also known as Tower of Brahma puzzle.

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 them 2^64 - 1 seconds or roughly 585 billion years.

There are many variations on this legend. For instance, in some stories the temple is a monastery and the priests are monks. The temple or monastery may be said to be in different parts of the world - including Hanoi, Vietnam 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.

Mathematical Significance

The problem of the Towers of Hanoi is isomorphic to finding a Hamiltonian path on a n-hypercube. The problem is solved by a remarkably simple recursive procedure. Further the terms of the sequence resembles the binary carry sequence. Amazingly, the number of discs moved after the kth step is the same as the element which needs to be added or deleted in the kth addend of the Ryser formula.

The number of steps required for n discs is 2^(n) - 1 which is the Mersenne numbers. Further this relates the Pascal's triangle to the Hanoi graph.

Significance in Computers

The problem of Towers of Hanoi is one the common methods of finding the speed of the computer. A code is written to solve the problem and the time taken for the computer to execute this code is used to determine the speed of the computer. You can try out the Towers of Hanoi here.