This famous puzzle consists of a fixed number of disks of different sizes, and three poles. The disks are initially stacked all on a single pole, with larger disks below successively smaller disks.
The objective of the puzzle is to move all disks from their initial pole to one of the other poles (say, the second one), one disk at a time, in such a way that no disk is ever on top of a smaller disk. All three poles may (and, in fact, must) be used, as long as the condition above is satisfied. Thus, for example, the top position in the figure below is legal, while the bottom one is not:
One of the reasons I wanted to show you this puzzle is that it is a perfect example of a problem that can be solved recursively. Since writing a computer program to solve this puzzle is one of the lab assignments, I will not show you here how to do it. However, I will give you a chance to play with it. The applet below is fairly simple to play with. Good luck and have fun!
© 2003 Wagner Truppel. All rights reserved.