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. 

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

This screenshot shows the program once it loads and the user has chosen to use 4 disks:

Here is the program while it is running. The disk that is about to move turns red:

This shows the 4 disks successfully moved to the right peg:

 

Getting Started

You can download the files TowersofHanoi.java, Peg.java, Disk.java and TowersofHanoi2.html to begin.  Wherever there is code that you need to write, you'll see a "TO DO".  This is an applet, and in Netbeans applets run better when you choose Run File instead of Run Project.