ECE 30 Programming Project Winter 2020
Cyclic Hanoi
due 6 pm Friday, March 13, 2020
The Tower of Hanoi is a mathematical game for moving a set of n disks stacked in the order of decreasing size from one pile to another (using a spare pile) one disk at a time without ever placing a larger disk on top of a smaller disk. The Cyclic Hanoi is derived from the Tower of Hanoi with a couple of restrictions:
1. There are 3 piles arranged in a circular fashion. 2. Disks can only be moved in a clockwise direction.
Pile A (Source)
Pile C (Spare)
Pile B (Destination)
1
The algorithm for moving n disks can best be described in a recursive manner as described below:
1. Move the top n − 1 disks to a spare pile.
2. Move the largest disk to the destination.
3. Move the n − 1 disks from the spare pile to the destination.
The algorithm becomes a bit more complex for the Cyclic Hanoi because of the second restriction: disks must be moved clockwise. Assuming that the disks are labeled from 1 to N from the smallest to the largest, to move n disks clockwise from pile A to pile B:
1. Move the top n − 1 disks counterclockwise to pile C.
2. Move disk N clockwise to pile B.
3. Move the n − 1 disks on pile C counterclockwise to pile B.
Note that moving of n−1 disks counterclockwise is figurative: individual disks can never be moved counterclockwise. To move n − 1 disks counterclockwise to the adjacent pile:
1. Move the top n − 2 disks counterclockwise to the target pile 2. Move disk N − 1 one step clockwise
3. Move the n − 2 disks clockwise to the start pile
4. Move disk N − 1 one step clockwise
5. Move the n − 2 disks counterclockwise to the target pile
The project consists of two parts: (1) to determine the minimum number of moves necessary to move n disks from pile A to pile B; (2) to simulate the game (the details of which will be discussed in class).
2
The number of moves it takes to complete a Tower of Hanoi game in the minimum number of steps can be calculated in a recursive manner as shown below.
int hanoi (int n)
{
if (n == 1)
return 1;
else
return 2 * hanoi(n – 1) + 1;
}
The simulation of a Cyclic Hanoi game can be set up using the following two proce- dures: move cw and move ccw for moving n disks from src pile to dst pile, clockwise and counterclockwise respectively.
/* dst = src’s neighbor clockwise */
void move_cw (int n, int src, int dst)
{
if (n > 1) {
move_ccw (n – 1, src, tmp);
move_cw (1, src, dst);
move_ccw (n – 1, tmp, dst);
} else if (n == 1) {
/* move one disk clockwise from src to dst */
} }
/* dst = src’s neighbor counterclockwise */
void move_ccw (int n, int src, int dst)
{
if (n > 1) {
move_ccw (n – 1, src, dst);
/* remainder of the algorithm intentionally left incomplete */
…
…
…
…
} else if (n == 1) {
move_cw (1, src, tmp);
move_cw (1, tmp, dst);
} }
3
Let the numbers of steps it takes to move n disks clockwise and counterclockwise be cw(n) and ccw(n) respectively. Then
cw(1) = 1 (1) ccw(1) = 2 (2) cw(n) = 2ccw(n−1)+1 (3) ccw(n) = 2ccw(n−1)+cw(n−1)+2 (4)
n
cw
ccw
1 2 3 4 5 ···
1
5 15 43 119 ···
2
7 21 59 163 ···
Extra Credit: complete the table above for n = 16. You must show how you obtained the solution: e.g., by providing the program for determining the results.
4
The piles should be implemented as stacks (that grow upward from lower memory address to higher). The capacity of each stack is 128 bytes (or 16 long integers). The base addresses of stacks A (source), B (destination), and C (temporary) are 0x000, 0x080, and 0x100 respectively. X19, X20, and X21 should be used as the stack pointer registers for stacks A, B, and C respectively. Each element of a stack represents the size of a disk: 1 for the smallest disk, 2 for the next larger one, etc. If the total number of disks to be moved is 10, the largest disk size is 10. The bottom of each stack is initialized with 255 to represent a disk with size 255, which is present for the purpose of size comparison when a disk is moved to an “empty” stack but is never meant to be moved. In addition, stack A is initialized with disks of size 1 to 10 as shown below.
1
2
3
4
5
6
7
8
9
10
255
255
255
SPA (X19)
0x050
SPB (X20)
0x080
SPC (X21)
0x100
When the Cyclic Tower of Hanoi game is completed, the stacks should look as below.
255
1
2
3
4
5
6
7
8
9
10
255
255
SPB (X20)
0x0D0
SPA (X19)
0x000
SPC (X21)
0x100
5