In an ancient city, so the legend goes, monks in a temple had to move a pile of 64 sacred disks from one location to another. The disks were fragile; only one could be carried at a time. A disk could not be placed on top of a smaller, less valuable disk. In addition, there was only one other location in the temple (besides the original and destination locations) sacred enough for a pile of disks to be placed there.
Using the intermediate location, the monks began to move disks back and forth from the original pile to the pile at the new location, always keeping the piles in order (largest on the bottom, smallest on the top). According to the legend, before the monks could make the final move to complete the new pile in the new location, the temple would turn to dust and the world would end.
Below is an applet program representing the task of moving a pile of disks from one tower to another.
Alternate game of Towers of Hanoi.
In previous labs we've been trying to get used to the idea of calling methods to get work done, often with those methods having been written by someone else. We'll do something similar here, we just won't type in any code to Eclipse. For this lab, assume that we're playing the Towers of Hanoi game with 3 towers labeled 0, 1, and 2. Also, suppose we have the following method:
moveSingleDisc(int from, int to, int spare)
This will take the top disk from the from tower, move it to the to tower, and leave the third tower spare unaffected. So, if I were to call moveSingleDisc(0, 1, 2) it would move the top disk from tower 0 onto the top of tower 1. Tower 2 would be left unaffected.
I can now use this method to write an algorithm for solving the Towers of Hanoi game. Consider a two-disk game were I want to move 2 disks from tower 0 onto tower 1. Of course, the larger disk can never be placed on top of the smaller disk. Here's how I might right such a method.
moveTwoDiscs(){
moveSingleDisc(0, 2, 1);
moveSingleDisc(0, 1, 2);
moveSingleDisc(2, 1, 0);
}
What did this do? I moved the smallest disk from tower 0 to tower 2, my spare tower, to get it out of the way. Then in the second call to "moveSingleDisc" I was free to move the remaining disk on tower 0 (the larger disk) from tower 0 to tower 1. Then, in the third call all I had left to do was move the smaller disk back from tower 2 onto tower 1. You can try following these steps yourself using the applet above, or the alternate Towers of Hanoi applet.
Note that I'm not confined to always moving discs from tower 0 to tower 1. I can have my method take in values just as the moveSingleDisc() method did. Then it can move disks from any of the three towers to any of the others.
moveTwoDiscs(int from, int to, int spare){
moveSingleDisc(from, spare, to);
moveSingleDisc(from, to, spare);
moveSingleDisc(spare, to, from);
}
Notice that, from my old method, I just repaced each 0 with the from variable, each 1 with the to variable and each 2 with the spare variable. With variables used instead of set numbers, my program can be told which tower to use for the roles of "from", "to" and "spare".
Question 1(A): Given the example program for solving a case with of this game with 2 disks, let's now consider solving it for a case with 3 disks. Try for yourself to solve a case with 3 disks using the applets provided above. Then, fill in the moveThreeDiscs(int from, int to, int spare) method below with the atomic steps you used. Represent each atomic step by calling the "moveSingleDisc()" method as used above. If doing this with variables is trick, first try writing your method using set numbers 0,1, and 2 as the "from", "to", and "spare" towers. Then, go back and replace each 0 with "from", each 1 with "to" and each 2 with "spare".
moveThreeDiscs(int from, int to, int spare){
moveSingleDisc( , , );
moveSingleDisc( , , );
moveSingleDisc( , , );
moveSingleDisc( , , );
moveSingleDisc( , , );
moveSingleDisc( , , );
moveSingleDisc( , , );
}
We've now written a basic algorithm for solving the Towers of Hanoi game for the case of 3 disks. There is an easier, or at least shorter, method we could write. To do this we'll now allow the use of calling the moveTwoDiscs() method as well as the moveSingleDisc() method. Remember that the moveTwoDiscs() method just made calls to moveSingleDisc() anyway, so all we're doing is pushing some work to another method written by someone else.
Question 1(B):
Fill in the code for the new moveThreeDiscs() method below, using only calls to either moveSingleDisc() or moveTwoDiscs. Once again, if using the variables is tricky, first try using 0's, 1's and 2's for the case of moving the 3 discs from tower 0 to tower 1 (using tower 2 as a spare). Then just replace the numbers with the appropriate variable names. Your code for this method should be shorter than the previous moveThreeDiscs() method (using about half as many lines).
moveThreeDiscs(int from, int to, int spare){
}
Question 1(C): Now that we've advanced the quality of our moveThreeDiscs() method we'll go just one basic step further: solving the case with 4 disks. Fill in code for the moveFourDisks() method below, using only calls to any of these methods: moveSingleDisc(), moveTwoDiscs(), or moveThreeDiscs(). You can call any of the methods as many times as you like, but your resulting code should actually be no longer than your advanced moveThreeDiscs() code was (i.e. only a few lines).
moveFourDiscs(int from, int to, int spare){
}
After writing algorithms for the cases of 2, 3, and 4-disk Towers of Hanoi problems, we should have built up some intuition for writing an algorithm to solve the general case of n-disk Towers of Hanoi. To do this we'll use a recursive algorithm, of course. For a recursive algorithm we need 2 things: (1) a recursive step (usually a method calling itself, and (2) one or more base cases (usually a test allowing the method to stop recursively calling itself).
Question 2(A): Consider the Towers of Hanoi problems we solved above. Describe a "recursive"-like step that we used in our algorithms to solve those problems. This may be easiest to describe in terms of n, n+1, n-1, etc. as the size of problem you were trying to solve or as the number of rings you were trying to move from one tower or another.
Question 2(B): For the algorithms that we used to solve the previous Towers of Hanoi cases above, describe a "base case"-like condition that was used. Again, this may be easiest to do if you consider a condition on some size n of discs that you were trying to move.
After trying to abstractly describe the properties in our previous algorithms that were "recursive-like", we're now ready to actually write a recursive algorithm. For our recursive method we'll be using solveHanoi():
solveHanoi(int from, int to, int spare, int numDiscs){
...
...
}
This method takes in almost the same information as our previous methods moveSingleDisc(), moveTwoDiscs(), moveThreeDiscs(), and moveFourDiscs(). The difference is that it takes one extra number for the size of the pile that its trying to move from the "from" tower onto the "to" tower. Previously we were implicitly doing this by calling a different method with the number included in the method's name.
Question 3(A):
Fill in the code for the solveHanoi() method below. It should be able to recursively move the discs on the from tower, to the to tower, using the spare tower as extra workspace. The only method calls that you should make are to the moveSingleDisc() method and to the solveHanoi() method itself. (Note: A method will behave differently depending on the input values it receives. This is important for a recursive method. If a recursive method calls itself, it must also have some base case to keep from always referring to itself and causing infinite recursion. The value held in the numDiscs variable may be helpful.)
solveHanoi(int from, int to, int spare, int numDiscs){
}
Question 3(B):
You've just written a complete, recursive algorithm for the Towers of Hanoi problem. Now we might ask, how fast does it run? Basically, we're interested in how many atomic steps the algorithm might take as a function of its input size n (which is held in the numDiscs variable). For this analysis, consider a single call to the moveSingleDisc() method as a single, atomic step.
As a function of the input size n, write how many atomic steps your algorithm will take. A general function (i.e. n vs n2 vs n3 vs ...) is more important than counting the 'exact' number of atomic steps. To gain intuition about this, see how many atomic steps your method takes for solving small cases with input sizes of 1, 2, 3, 4, etc. then look for patterns for how the number of steps taken grows with the input size. (Note: The number of steps your algorithm takes on, for example, an input size of 4 should be similar to the number of steps taken by the moveFourDiscs() method.)