Lab 20: Stacks of Hanoi
Intro
You’ll work in this lab with your lab partners.
The two of you will work as a team to solve problems. At any time, one of you will be the Head and the other will be the Hands. The Head does the thinking and the Hands does the typing. Hands type only what the Head tells them to, but you’re free to discuss any issues that pop up. You should switch off during the lab to make sure each of you get practice problem solving, dealing with syntax, and getting finger exercises on the keyboard.
You should start this lab with this project skeleton.
Tower of Hanoi
The Tower of Hanoi is simple puzzle. There are three posts: the leftmost starts with a stack of rings ordered in ascending width. The goal is to move the rings from the leftmost to another post.
The rules of the game:
Only one ring can be moved at a time.
Only the topmost ring of any tower can be moved.
Each ring can only be placed on a larger ring.
We’re going to implement this game using ordered stacks in an imperative world. The partially finished Hanoi implementing World is given in Lab20.java.
The classes found in Listof.java and Stackof.java are mostly unchanged from Lab 19: Stacks of Stuff. The given classes Ring and Tower are simple and need not be changed. Look them over to understand their purpose.
Ex 1: Implement the method Hanoi.moveRing. Remember, you can only make the move if the tower from has a ring and the topmost ring on the tower to has either no ring or a larger ring. Hint: A good design starts by creating the method Boolean OrdStackof.canPush(X x), which returns true if the element x can be pushed onto this ordered stack (leaving the stack unchanged).
Ex 2: The definition of canPush looks a lot like void OrdStackof.push(X x); reimplement push to use canPush if you haven’t already.
Ex 3: Implement the game logic in Hanoi.onMouseClicked. In our game, we first select some source tower (with a ring on it) by clicking it, then click on the tower to which we will move the topmost ring of the source. The translation between the mouse event and the tower that was clicked is already given. You only need to implement the game logic to select source and destination towers.
Ex 4: The current Hanoi class has a hardcoded number of rings: 3. Generalize the class to work for an arbitrary number of rings.
Ex 5: The current Hanoi class has a hardcoded number of towers: 3. Generalize the class to work for an arbitrary number of towers.