Mathematical Preliminaries - Data Structures and Algorithm Analysis - page 35

(A) (B)

Figure2.2 Towers of Hanoi example. (a) The initial conditions for a problem
with six rings. (b) A necessary intermediate step on the road to a solution.

The Towers of Hanoi puzzle begins with three poles and n rings, where all rings
start on the leftmost pole (labeled Pole 1). The rings each have a different size, and
are stacked in order of decreasing size with the largest ring at the bottom, as shown
in Figure 2.2(a). The problem is to move the rings from the leftmost pole to the
rightmost pole (labeled Pole 3) in a series of steps. At each step the top ring on
some pole is moved to another pole. There is one limitation on where rings may be
moved: A ring can never be moved on top of a smaller ring.
How can you solve this problem? It is easy if you don't think too hard about
the details. Instead, consider that all rings are to be moved from Pole 1 to Pole 3.
It is not possible to do this without first moving the bottom (largest) ring to Pole 3.
To do that, Pole 3 must be empty, and only the bottom ring can be on Pole 1.
The remaining n 1 rings must be stacked up in order on Pole 2, as shown in
Figure 2.2(b). How can you do this? Assume that a function X is available to
solve the problem of moving the top n1 rings from Pole 1 to Pole 2. Then move
the bottom ring from Pole 1 to Pole 3. Finally, again use function X to move the
remaining n1 rings from Pole 2 to Pole 3. In both cases, “function X” is simply
the Towers of Hanoi function called on a smaller version of the problem.
The secret to success is relying on the Towers of Hanoi algorithm to do the
work for you. You need not be concerned about the gory details of how the Towers
of Hanoi subproblem will be solved. That will take care of itself provided that two
things are done. First, there must be a base case (what to do if there is only one
ring) so that the recursive process will not go on forever. Second, the recursive call
to Towers of Hanoi can only be used to solve a smaller problem, and then only one
of the proper form (one that meets the original definition for the Towers of Hanoi
problem, assuming appropriate renaming of the poles).
Here is an implementation for the recursive Towers of Hanoi algorithm. Func-
tion move(start,goal) takes the top ring from Pole start and moves it to
Pole goal . If move were to print the values of its parameters, then the result of
calling TOH would be a list of ring-moving instructions that solves the problem.