tower of hanoi

2005.05.12

Douglas Edric Stanley

> source code: tower_of_hanoi

This diagram illustrates one of the fundamental principles of computer sciences, namely a simple but strict looping form of recursion. In fact this algorithm is often used to teach computer programming, and specifically recursive computer programs.

Tower of Hanoi

The Tower of Hanoi — also known as the Tower of Brahma — is a puzzle designed by the french mathematician Edouard Lucas in 1883. Its rules are simple. A series of successively smaller plates are stacked one atop the other and are strung onto one of three poles via a central hole on the middle of each plate. Beginning from this starting position, the player tries to move all of the plates to one of the two other poles. However, there are two constraints: the player can only move one plate at a time, and the plates cannot be stacked onto plates smaller than themselves.

There is a legend that accompagnies this puzzle, concerning nothing less than the destruction of the world:

D'après une vieille légende Indienne, les brahmines se succédent depuis bien longtemps, sur les marches de l'autel dans le Temple de Bérnares pour exécuter le déplacement de la Tour Sacrée de Brahma, aux soixante quatre pages en or fin, garnis de diamants de Golconde. Quand tout sera fini, la Tour et les
Brahmines tomberont, et ce sera la fin du monde!
– Professeur N. Claus (de Siam), a.k.a. Édouard Lucas; La tour d'Hanoï: Véritable casse-tête annamite; 1883; pp. 2

According to Lucas, the Tower_of_Hanoi originated in India, with the Brahmines displacing each sacred plate of Brahma, one by one, so as not to break the sacred texts decorated in gold. When the monks will have finished, apparently the Tower will fall, along with the Brahmines as well as the rest of the world. Although this plot sounds particularly sinister, there is no need to worry, as the entire process exponentially brings us to billions of years (thanks to the number of pages that must be recursively moved by the monks).