Project 1, CISC181 honors, Spring 2004

The Towers of Hanoi

The "Towers of Hanoi" problem is a famous problem in Computer Science. It is described in your Deitel/Deitel textbook, on p. 246, in problem number 3.42. Project one will involve solving this problem, but with a few twists.

First, a description of the problem. There are n disks, each a different size, and three pegs. The disks have a hole in the middle (like a donut).

At the beginning, they are all stacked on one of the three pegs, in order of size, with the largest disk on bottom, and the smallest on top. The following diagram shows how it might look if n is 4:


    |           |            |    
   =|=          |            |    
  ==|==         |            |    
 ===|===        |            |    
====|====       |            |    
----+----   ----+----    ----+----

The object of the game is to get all the pegs from peg 1 to peg 2, with the following constraints:

Exactly one disk is moved at a time; only one disk can be "off the pegs" at any point in time.
A third peg is available for temporarily holding disks.
You must always place smaller disks on top of larger ones; never the other way around. This is true for the third "temporary" peg as well.

So here is an example of the goal:


      |          |           |    
      |         =|=          |    
      |        ==|==         |    
      |       ===|===        |    
      |      ====|====       |    
  ----+----  ----+----   ----+----

Here's an example of a legal intermediate state:


      |          |           |    
      |          |           |
      |          |           |  
      |       ===|===       =|=         
      |      ====|====     ==|==        
  ----+----  ----+----   ----+----

Here's an example of a forbidden intermediate state:


      |          |           |    
      |          |           |
      |          |           |  
      |      ====|====     ==|==         
      |       ===|===       =|=        
  ----+----  ----+----   ----+----

Got the picture? Good.

Now, your task is to write a program, that for any value of n will solve the Towers of Hanoi problem. Your program should conform to all the rules specified in the textbook for problem 3.42 on pp. 246-247, which offers some great hints for solving the problem.

One of the rules listed there is that the program should print out each move that is required, as you proceed through the solution. For example, to solve the problem for 3 disks, the following is legal set of moves to get all the disks from peg 1 to peg 2:

1 -> 2
1 -> 3
2 -> 3
1 -> 2
3 -> 1
3 -> 2
1 -> 2

(Note that that sequence is different from the "legal one" in your text, which shows how to move disks from peg 1 to peg 3.)

Each line a -> b in the output above means "move a disk from peg a to peg b".

The extra twist is this:

If n<=10, offer the user an option (yes or no) to display the starting position as "ASCII art", and then also display the result after each move is made.

For example, here's the starting position, for n=10.

         =|=                    |                     |
        ==|==                   |                     |
       ===|===                  |                     |
      ====|====                 |                     |
     =====|=====                |                     |
    ======|======               |                     |
   =======|=======              |                     |
  ========|========             |                     |
 =========|=========            |                     |
==========|==========           |                     |
----------+---------- ----------+---------- ----------+----------

And here's how the disks would look after the move 1 -> 2 (which is not necessarily the correct first move for n=10; maybe it is, and maybe it isn't. :-) ):

          |                     |                     |
        ==|==                   |                     |
       ===|===                  |                     |
      ====|====                 |                     |
     =====|=====                |                     |
    ======|======               |                     |
   =======|=======              |                     |
  ========|========             |                     |
 =========|=========            |                     |
==========|==========          =|=                    |
----------+---------- ----------+---------- ----------+----------

The reason for the restriction n<=10 is probably obvious: for n>10, the screen will start to get a bit cluttered! Also, the length of the output will get a bit ridiculous (actually, that will probably happen long before you get to n=10.)

I strongly encourage you to start by writing a function:

displayDisks(int n, int disks[]);

that will print out a diagram of the towers, where n is the total number of disks, and disks is an array where disks[i] represents which of the three pegs (0, 1 or 2) is the current home of that disk. It is probably better if you number the disks 0 through n-1 instead of 1 through n).

Get that function working first, and write a small little test program to show that it works for various values of the disks[] array. A working version of that function, and a small driver program that shows it works is worth 50% partial credit, and if you run into trouble with the rest, that is much better than a zero!

Alternatively, a program that solves the towers of hanoi, but produces ONLY the output for the moves (not the graphical illustration in ASCII art) is also worth 50% partial credit. So my suggestion is: tackle the problems independently first, and THEN combine your solutions.

Grading

50% of your grade is for the correctly formatted output, and 50% is for the solution to the Towers of Hanoi problem itself.
For each of the two parts, 50% of your grade is for correctness, and 50% for style (including but not limited to comments and indentation).

Phillip T Conrad

Last modified: Thu Mar 11 15:29:22 EST 2004