Towers of Hanoi

15 points

The Towers of Hanoi is a classic recursive program.  The problem involves 3 pegs.  The leftmost peg begins with a certain number of disks, while the other 2 pegs are empty.  The challenge is to move all the disks to the rightmost peg. 

Here is one visualization of the Towers of Hanoi; there are others.

The following describes the Towers of Hanoi well; it is from Visual Basic 6.0 by Kerman and Brown:

The Towers of Hanoi is a classic problem that has a simple recursive solution.  The game consists of a board with three pegs (A, B and C) and a certain number of disks.  The game begins with all disks on peg A.  The object is to move all disks to peg C according to the following rules:

        1. One disk is moved at a time.
        2. A disk can only be placed on top of one that is larger in size.

Now take a few minutes and try to develop an algorithm to solve this problem.  Think about this problem for one disk, two disks and three disks.  Do you see any patterns?

For one disk, the solution is trivial: Move the disk from peg A to peg C.

How about for two disks?  Move the first disk from peg A to peg B.  Then, move the second disk from peg A to peg C.  Finally, move the first disk from peg B to peg C.  Note that the first and last steps repeat the solution for the one-disk case. 

Now, how about for three disks?  Obviously the solution is longer, but it contains the solution to the two-disk case: Use the two-disk solution to move two disks from peg A to peg B.  Then, move the third disk from peg A to peg C.  Finally, use the two-disk solution to move two disks from peg B to peg C.  Again, notice the references to the previous solution.  The general solution algorithm follows:

        1. Use the (n-1)-disk solution to move (n-1) disks from peg A to peg B.
        2. Move disk n from peg A to peg C.
        3. Use the (n-1)-disk solution to move (n-1) disks from peg B to peg C.

Screenshots

We will be printing the output from the Towers of Hanoi program to the Output window.

Below is a screenshot of the 2-disk solution, where # signs represent each disk.

Below is a screenshot of the 3-disk solution.

Getting Started

You can download the files TowersOfHanoi.java, Peg.java, and Disk.java to begin.  Wherever there is code that you need to write, you'll see a "TO DO". 

Extra Credit (2 points)

An extra-credit option is to display the step number of the animation. You'll see this number in the screenshots above.