You should have one class called "Tower" and another class called "Disk".
The main program should call a recursive function that moves n disks from the source tower to the destination tower, using a third tower as an intermediate.
The description of the problem below is only a guideline; you do not need to follow it "exactly" (e.g. in terms of details of formatting of output, etc.) as long as your solution is roughly equivalent.
See also, the description of lab09.
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:
| | |
| =|= |
| ==|== |
| ===|=== |
| ====|==== |
----+---- ----+---- ----+----
Here's an example of a legal intermediate state:
| | |
| | |
| | |
| ===|=== =|=
| ====|==== ==|==
----+---- ----+---- ----+----
Here's an example of a forbidden intermediate state:
| | |
| | |
| | |
| ====|==== ==|==
| ===|=== =|=
----+---- ----+---- ----+----
Now, your task is to write a program, that for any value of n will solve the Towers of Hanoi problem.
Your 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 the 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:
=|= | |
==|== | |
===|=== | |
====|==== | |
=====|===== | |
======|====== | |
=======|======= | |
========|======== | |
=========|========= | |
==========|========== | |
----------+---------- ----------+---------- ----------+----------
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[]);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.