Recursive and Non-recursive C and C++ Source Code for the Tower of Hanoi Algorithm - Full-text Search Blog

by minidxer on 2008-01-30 08:00:02

The Tower of Hanoi (also known as the Tower of Brahma) problem is actually an ancient Indian legend. The god Brahma, who created the universe (similar to Pangu in Chinese mythology), left three diamond rods in a temple. On the first rod, there were 64 circular gold discs stacked, with the largest one at the bottom and each subsequent one getting smaller, stacked sequentially on top of each other. The monks in the temple tirelessly moved them one by one from one rod to another, following the rules: they could use the middle rod as an auxiliary, but only one disc could be moved at a time, and a larger disc could never be placed on top of a smaller one.

The resulting calculation is incredibly astonishing (the number of moves required): **18,446,744,073,709,551,615**. Even if the monks devoted their entire lives to this task, it would be impossible for them to complete moving all the gold discs.