Description
Introduction
The Tower of Hanoi1
, is a mathematical game or puzzle. It consists of three towers, and a number
of discs of different sizes which can be slide onto any rod. The puzzle starts with the discs in a neat
stack in ascending order of size on one rod, the smallest at the top, the making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following
simple rules:
1. Only one disc can be moved at a time.
2. Each move consists of taking the upper disc from one of the stacks and placing it on top of
another stack (i.e., a disc can only be moved if it is the uppermost disc on a stack).
3. No disc may be placed on top of a smaller disc.
With three discs, the puzzle can be solved in seven moves. The minimum number of moves required
to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of discs.
What to do
For this lab, imagine that we are going to use computer to solve Tower of Hanoi puzzle. To do so,
we need a way to represent the Tower of Hanoi puzzle in computer. In the real world, the Tower
of Hanoi puzzle is an object consists of three towers (rod), and a number of discs where
each disc can be uniquely identified by its color and size. Since we are using Java which is
an Object-Oriented Programming, why don’t we construct an object that can be used to represent
the actual Tower of Hanoi puzzle.
To do so, we need a class. Let’s call this TowerOfHanoi. The starter file for this class can
be found in TowerOfHanoi.java. An instance of this class can be constructed by specifying the
number of discs (n). After it is constructed, it consist of the following:
• three towers where each tower can be uniquely identify by an integer number 0, 1, or 2, and
• n discs where each disc can be uniquely identify by an integer number between 0 to n − 1.
The disc number 0 is always the smallest disc. Note that all discs should be on tower
0 and no disc on tower 1 and tower 2.
Operations that we can perform on this Table of Hanoi puzzle are as follows:
• public int getNumberOfDiscs(): We can check the number of discs in the Tower of Hanoi
puzzle (total number of discs).
1From Wikipedia
CS/COE 0445 — Data Structure Page 1
Lab 6: Permutation using Recursion
• public int getNumberOfDiscs(int tower): We can check the number of discs in each
tower.
• public int[] getArrayOfDiscs(int tower): We can check the order of discs in each
tower. This results in an array of integer where the size of the array is the number of discs
in the tower and the content of the array are disc ID numbers. The first element in the array
should be the disc ID number of the disc that is located at the bottom of the tower. Thus,
the last element in the array should be the disc ID number of the disc that is located at the
top of the tower.
• public void moveTopDisc(int fromTower, int toTower): We can move the top disc from
one tower (fromTower) to another tower (toTower). This operation should return true if all
of these conditions are met:
1. fromTower contains at least one disc, and
2. the toTower contains no disc or the top disc of toTower is larger than the top disc of
fromTower unless the fromTower and toTower are the same tower.
Otherwise, this operation should return false and no disc should be moved.
Example
Suppose a user construct the Tower of Hanoi using the following statement:
TowerOfHanoi toh = new TowerOfHanoi(7);
After the above statement, toh can be represented by the Tower of Hanoi puzzle shown in Figure 1
(a). Return values of each method should be as follows:
Method Return Value
toh.getNumberOfdiscs() 7
toh.getNumberOfdiscs(0) 7
toh.getArrayOfdiscs(0) [6,5,4,3,2,1,0]
toh.getNumberOfdiscs(1) 0
toh.getArrayOfdiscs(1) []
toh.getNumberOfdiscs(2) 0
toh.getArrayOfdiscs(2) []
If a user wants to move the top disc from tower 0 to tower 1, the following statement should be
used (assuming that the variable named returnValue of type boolean has be declared earlier:
returnValue = toh.moveTopdisc(0,1);
In this case returnValue should be true and the Table of Hanoi puzzle should look like Figure 1
(b). Return values of each method should be as follows:
CS/COE 0445 — Data Structure Page 2
Lab 6: Permutation using Recursion
(a) (b)
(c) (d)
Figure 1: Tower of Hanoi Puzzle
Method Return Value
toh.getNumberOfdiscs() 7
toh.getNumberOfdiscs(0) 6
toh.getArrayOfdiscs(0) [6,5,4,3,2,1]
toh.getNumberOfdiscs(1) 1
toh.getArrayOfdiscs(1) [0]
toh.getNumberOfdiscs(2) 0
toh.getArrayOfdiscs(2) []
If a user wants to move the top disc from tower 0 to tower 2, the following statement should be
used (assuming that the variable named returnValue of type boolean has be declared earlier:
returnValue = toh.moveTopdisc(0,2);
In this case returnValue should be true and the Table of Hanoi puzzle should look like Figure 1
(c). Return values of each method should be as follows:
Method Return Value
toh.getNumberOfdiscs() 7
toh.getNumberOfdiscs(0) 6
toh.getArrayOfdiscs(0) [6,5,4,3,2]
toh.getNumberOfdiscs(1) 1
toh.getArrayOfdiscs(1) [0]
toh.getNumberOfdiscs(2) 1
toh.getArrayOfdiscs(2) [1]
If a user wants to move the top disc from tower 1 to tower 2, the following statement should be
used (assuming that the variable named returnValue of type boolean has be declared earlier:
returnValue = toh.moveTopdisc(1,2);
In this case returnValue should be true and the Table of Hanoi puzzle should look like Figure 1
(d). Return values of each method should be as follows:
CS/COE 0445 — Data Structure Page 3
Lab 6: Permutation using Recursion
Method Return Value
toh.getNumberOfdiscs() 7
toh.getNumberOfdiscs(0) 6
toh.getArrayOfdiscs(0) [6,5,4,3,2]
toh.getNumberOfdiscs(1) 0
toh.getArrayOfdiscs(1) []
toh.getNumberOfdiscs(2) 2
toh.getArrayOfdiscs(2) [1,0]
Test Class
A test class (TowersTester.java) is provided. Simply compile and run this test class. This
program will test your TowerOfHanoi.java and show your total points (out of 10). If you do not
get the full 10 points, you should keep trying to fix your code until you get 10 points. Note that
this test class is not perfect.
It cannot tell you why your program is incorrect. You may have to
look at the source code of TowersTester.java and see why it says FAIL and trace your code.
If your TowerOfHanoi.java works correctly, you can run THFrame.java to see an animation of
Due Date and Submission
For the due date, please check the lab in the CourseWeb. Submit your Permutation.java to the
CourseWeb under this lab by the due date. No late submission will be accepted.
CS/COE 0445 — Data Structure Page 4
