From your Prelab, you should have learned about the concept of recursion and that using a recursive algorithm to solve problems is sometimes more efficient than trying to iterate the steps in a loop. For this lab, you will implement a recursive solution to the Towers of Hanoi problem.
You first need to set a CLASSPATH environment variable to link to the awb directory and the classes provided there. To set up your class path type in the following command at the prompt:
~jforbes/bin/setclasspath
Type logout to log out and press <Enter> to log in again.
Create a lab7 directory in your cps001 directory.
Copy the file awb.jar into your cps001/lab7 directory from
/afs/acpub.duke.edu/project/web/cps001/code/
Copy the Towers of Hanoi files into your cps001/lab7 directory. The files to be copied are TowersOfHanoi.java and TowersOfHanoi.html, which are located here:
/afs/acpub.duke.edu/project/web/cps001/code/lab7/
Open TowersOfHanoi.java with XEmacs.
TowersOfHanoi.java is the file you will modify to solve the Towers of Hanoi. There will be a lot of terminology in the file that you might not understand, especially the area below the indicated line. The important thing is to understand the subroutine MoveSingleDisc(int from, int to) moves a single disc from the specified from tower to the specified to tower. The other subroutine is the MoveDiscs(int from, int to, int aux, int n).
int from represents the starting tower.
int to represents the destination tower.
int aux represents the auxiliary or intermediate storage tower.
int n represents the number of discs to move.
For your recursive solution, you must think about how these towers are related to each other as you go through each step of the recursion and how their roles will switch. You will fill in the subroutine MoveDiscs to solve the problem.
As pointed out in the Prelab, all recursive solutions need a BASE CASE! This is how the algorithm terminates itself, as the base case makes no recursive call (else you would have something like an infinite loop).
What is the base case for Towers of Hanoi? What needs to be done in this case? How do we reach the base case?
From your Prelab you should be able to determine an algorithm that would help you solve the problem. To get you thinking more about the problem ponder this INCORRECT recursive solution and think about why it is incorrect:
Incorrect solution: Move the first disc to temporary storage, make a recursive call to move the rest of the discs to the destination tower and then move the first disc to to the final tower.
Try it out and see what problems you encounter. What is the CORRECT recursive solution to avoid this problem? You can test your solution iteratively here.
Now that you've come up with a good algorithm for solving the Towers of Hanoi problem, it is now time to code it up. As we mentioned before, you can ignore the rest of the code and just go to the subroutine MoveDiscs(int from, int to, int aux, int n).
Fill in your solution for the base case (what has to Happen when there is only one disc or n==1?). Then write the solution for the recursive case. Remember that to move one disc you call on the subroutine MoveSingleDisc(int from, int to).
Compile TowersOfHanoi.java and run
appletviewer TowersOfHanoi.html
Test your algorithm! The button <AutoSolve> should automatically solve the problem for any inputted number of discs.
Submit the files TowersOfHanoi.java and TowersOfHanoi.html as follows:
submit_cps001 lab7/sec# TowersOfHanoi.java TowersOfHanoi.html
Replace # with your section number. DON'T FORGET TO INCLUDE YOUR NAME AND
LAB SECTION AT THE TOP OF ALL OF YOUR FILES!