Tower of Hanoi
The "Tower of Hanoi" problem refers to an ancient eastern story, or myth. It goes as follows:
- There are three pegs, the first one containing a certain number of disks, one on top of the other, each upper one smaller than the lower one. The other two pegs are empty.
- You are to move all disks from the first peg to the last
one, but you must follow these rules:
- at each move you can only move one disk to any of the three pegs
- at no time should a larger disk be on top of a smaller one
The story goes that if you physically move 64 disks from one peg to another according to these rules the world will come to an end.
You can click on a peg to select a disk to move from, then click on the second peg to move the disk to that peg. Or you click the Solve button to have the algorithm solve your problem - and end the world?
As it turns out, it is easy to describe a recursive algorithm to solve the "tower of Hanoi" problem, for any number of disks. Above is a Java applet that uses this algorithm. Why don't you try try to bring the world to an end ?