Subsection 6.2.7 The Towers of Hanoi
To see how we can use those things to specify a program, let’s look at a fun example that isn’t exactly going to shake up the computer industry. But it’s an interesting problem to write a program to solve.
We want to write a program to solve the Towers of Hanoi problem.
Various stories have been created to go along with the problem. One version is the following:
In a monastery in India there are three poles and 64 golden disks, each of a different diameter. When God created the universe, he stacked the disks on the first of the poles, with the largest on the bottom. The remaining disks were stacked in order of size, with the smallest on the top. The monks were given the task of moving all 64 disks to the last pole. But the disks are sacred, so there are important rules that must be followed. Whenever a disk is removed from a pole, it must immediately be placed on some other pole. No disks may be placed on the ground or held. Further, a disk may never be placed on top of a smaller disk. The monks were told that they must begin working immediately, taking turns around the clock. When they finish, the world will end.
Nifty Aside
The Towers of Hanoi problem was invented by François Édouard Anatole Lucas, who published it in 1883 under the name of N. Claus of Siam. Can you describe a procedure to solve it?