Programming and Problem Solving with Java

(^644) | Recursion
Next, we examine a more complicated problem—one in which the recursive solution is
not immediately apparent.

Towers of Hanoi

One of your first toys may have been a board with three pegs holding colored circles of dif-

ferent diameters. If so, you probably spent countless hours moving the circles from one peg

to another. If we put some constraints on how the circles or discs can be moved, we have an

adult game called the Towers of Hanoi.

When the game begins, all the circles are on the first peg in order by size, with the small-

est on the top.The object of the game is to move the circles, one at a time, to the third peg.The

catch is that a circle cannot be placed on top of one that is smaller in diameter. We can use the

middle peg as an auxiliary peg, but it must be empty at the beginning and end of the game.

To get a feel for how this problem might be resolved, let’s look at some sketches of what

the configuration must be at certain points if a solution is possible. We use four circles or discs.

The beginning configuration is

To move the largest circle (circle 4) to peg 3, we must move the three smaller circles to peg

2. Then we can move circle 4 into its final place:

Let’s assume we can do this. Now, to move the next largest circle (circle 3) into place, we

must move the two circles on top of it onto an auxiliary peg (peg 1, in this case):

To get circle 2 into place, we must move circle 1 to another peg, freeing circle 2 to be moved

to its place on peg 3:

2 3

1

12 3 123

4 4

3

2

1

3

2

1

12 3 123

4 3 4

2

1

4

3

2

1

12 3