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.
TowersOfHanoi.java is the file you will modify to solve the Towers of Hanoi. You need to fill in the code for the MoveDiscs subroutine:
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. To move a single disc, you can call the subroutine MoveSingleDisc(int from, int to) moves a single disc from the specified from tower to the specified to tower (this subroutine is already implemented for you).
As pointed out in the Prelab, all recursive solutions need a BASE CASE! This is how the algorithm terminates, 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).
Save TowersOfHanoi.java and run it as an applet.
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 using assignment name lab8.
DON'T FORGET TO INCLUDE YOUR NAME AND
LAB SECTION AT THE TOP OF ALL OF YOUR FILES!