CSCI 150 Homework 6

Due Friday, March 21, at the beginning of class.

Introduction
In this assignment you will write a program to solve the Tower of Hanoi puzzle for any given number of rings. In this puzzle, you are presented with a stack of rings on a peg, arranged from largest to smallest, with the largest ring on the bottom, and the smallest ring on the top. There are two other empty pegs available. The goal of the puzzle is to move all the rings from the first peg (peg 'A') to the second peg (peg 'B') making use of the spare peg (peg 'C'). You may only move one ring at a time, and you cannot put a ring on top of a ring that is smaller than it is. We will accomplish this with a recursive program. We can describe the solution in English as follows: If the tower is only one disk high, move it from peg 'A' to peg 'B'. Otherwise, first move all the disks except the bottom one from peg 'A' to peg 'C' (this is just a smaller version of the original problem). Then move the bottom ring from peg 'A' to peg 'B'. Finally, move the smaller tower of disks from peg 'C' to peg 'B'. The goal of this homework is to gain some practice in writing a recursive procedure.

Program Description
The program will prompt the user for the number of rings to use for the puzzle. It should then output the sequence of moves that a person should make to solve the puzzle for that many rings. For example, one move would be written as:

Move ring 4 from peg A to peg C.

The result of running the program should be a list of instructions that can be followed to solve the puzzle.

Project Specifications
Place all your code in a file named <username>_puzzle.pas, where <username> refers to your own username. For example, Professor Royden's file would be named croyden_hanoi.pas.

Your program should consist of a very short main program, that prompts the user for the number of rings to be used in the puzzle. It will then call a procedure, named Hanoi( ) which will solve the puzzle for moving from peg 'A' to peg 'B' using peg 'C' as a spare.

The Hanoi() procedure should take 4 parameters: The number of rings to move and three characters. The first character indicates the label of the 'source' peg (from which you are moving the stack of rings). The second character indicates the 'destination' peg (the peg to which you are moving the stack of rings). The third character indicates the 'spare' peg. Thus, you could move a stack of 3 rings from peg 'A' to peg 'B' using peg 'C' as a spare with the following call to Hanoi():

Hanoi(3, 'A', 'B', 'C');

You do not need any other parameters or local variables for this procedure. The procedure should use the recursive strategy described above to solve the Hanoi( ) puzzle for the given number of rings. This procedure should be fairly short (not more than about 15 lines of code altogether).

You can make use of the following procedure to move a ring from one peg to another:

procedure moveRing(ring : integer; fromPeg : char; toPeg : char);
begin
	writeln('Move ring ', ring, ' from peg ', fromPeg, ' to peg ', toPeg, '.');
end;

Note: you should put the moveRing() procedure definition in your program before the definition for the Hanoi( ) procedure. Otherwise, the Hanoi() procedure will not recognize it.

Sample Output
Your output should be as follows:
Sample output 1:

How many rings are in the tower?
2
Move ring 1 from peg A to peg C.
Move ring 2 from peg A to peg B.
Move ring 1 from peg C to peg B.

Sample output 2:

How many rings are in the tower?
4
Move ring 1 from peg A to peg C.
Move ring 2 from peg A to peg B.
Move ring 1 from peg C to peg B.
Move ring 3 from peg A to peg C.
Move ring 1 from peg B to peg A.
Move ring 2 from peg B to peg C.
Move ring 1 from peg A to peg C.
Move ring 4 from peg A to peg B.
Move ring 1 from peg C to peg B.
Move ring 2 from peg C to peg A.
Move ring 1 from peg B to peg A.
Move ring 3 from peg C to peg B.
Move ring 1 from peg A to peg C.
Move ring 2 from peg A to peg B.
Move ring 1 from peg C to peg B.

To Submit Your Finished Project:
1. Hand in a hard copy of the file <username>_puzzle.pas. Hand this to your instructor in class on the project's due date.

3. Hand in a printout of 2 sample runs like those shown above. Hand this to your instructor in class on the project's due date.

4. Print your name at the top of the cover page and staple it to the top of your hard copy.

5. In addition to the hard copy mentioned above, email your <username>_puzzle.pas file to me at croyden@mathcs.holycross.edu

Get started early and have fun!