First we make the convention that 0 will denote clockwise movement and 1 anticlockwise movement. Now, we need to design two new functions: Opp, that will return the opposite direction and Neigh which is the number of the pole that is the neighbor of the current pole. Function Opposite is easy to implement:
static int Opposite(int dir) { return (dir==1) ? 0 : 1; }
The neighbor of a pole is calculated by adding to its number the the neighbor's direction; then the neighbor's number is obtained by dividing the sum by 3 plus 1 (can you think why?).
static int Neighbor(int Pole, int dir) { return (Pole + dir) % 3 +1; }
Under this new consideration, we must change the definition of procedures hanoi and moveDisk:
static void hanoi(int height, int Pole, int dir) { if (height >= 1) { hanoi(height-1, Pole, Opposite(dir)); moveDisk(height, Pole, dir); hanoi(height-1, Neighbor(Pole, Opposite(dir)), Opposite(dir)); } } static void moveDisk(int disk, int fromPole, int dir) { char fromPeg = PoleName(fromPole), toPeg = PoleName(Neigh(fromPole, dir)); moves++; System.out.print(fromPeg); System.out.print(toPeg); System.out.print(((moves % 20)==0) ? '\n' : ' '); } static char PoleName(int pole) { switch (pole) { case 1: return 'A'; case 2: return 'B'; case 3: return 'C'; } return 'E'; }
Back to main page
Get the source code
As it was explained in the main text we can eliminate the use of the variable dir and consequently we don't need function Opposite. Let's see how procedures hanoi and moveDisk are transformed:
static void hanoi(int height, int Pole) { if (height >= 1) { hanoi(height-1, Pole); moveDisk(height, Pole); hanoi(height-1, Neigh(Pole, (TowerHeight - height+1) %2 )); } } static void moveDisk(int disk, int fromPole) { char fromPeg = PoleName(fromPole), toPeg = PoleName(Neigh(fromPole, (TowerHeight - disk) % 2)); moves++; System.out.print(fromPeg); System.out.print(toPeg); System.out.print(((moves % 20)==0) ? '\n' : ' '); }
Variable TowerHeight is a global static variable that holds the initial height of the tower.
Back to main page
Get the source code
We now eliminate the second argument. First we must declare one more global variable and then we must find the which expression is used an argument and what's the inverse of this expression. Global variables in Java are just class variables and there usually declared at the beginning of the definition of a class, i.e.,
The expression we are seeking and its inverse are:
Expression | Inverse Expression |
Neighbor((TowerHeight - disk) % 2) | Neighbor((TowerHeight - disk + 1) % 2) |
Now, we are have to assign to the global variable Pole the expression before the recursive call and after that we reassign to it the inverse expression. Procedure hanoi is therefore altered:
static void hanoi(int height) { if (height >= 1) { hanoi(height-1); moveDisk(height); Pole = Neighbor((TowerHeight - height + 1) %2); hanoi(height-1); Pole = Neighbor((TowerHeight - height) %2); } }
As it is evident both Neighbor and moveDisk have been adapted to access variable Pole globally.
Back to main page
Get the source code
Before we actually remove recursion we must remove the postorder statement, i.e., we want to transform the recursive procedure
void C(xtype x) { if(P(x)) { C(F1(x)); S1(x); C(F2(x)); S2(x); } }
into the following one provided there is an inverse to expression F1:
void C(xtype x) { if(P(x)) { C(F1(x)); x1 = x; for(; P(x) ;) x1 = F1(x1); for(; x1 != x ;) { S2(x1); x1 = inv(F1)(x1); } S1(x); C(F2(x)); } }
Although the resulting procedure is far more complex than the original one, if we transform procedure hanoi of the previous section, we get a really simpler procedure. First note that the first loop becomes:
height1 = height; for (; height1 != 0; ) height1--;
which means that we simply assign to variable height1 the value 0! The other loop becomes:
for(; height1 != height; height1++) Pole = Neighbor((TowerHeight - height1) %2);
Which is equivalent with the following command sequence, given that height1 is initially set to zero:
Pole = Neighbor((TowerHeight) %2); Pole = Neighbor((TowerHeight - 1) %2); Pole = Neighbor((TowerHeight - 2) %2); .... .... Pole = Neighbor((TowerHeight - height) %2);
The total effect of the above commands is null if height is odd. In case height is even the command sequence reduces to the last command. Thus we have for procedure hanoi:
static void hanoi(int height) { if (height <> 0) { hanoi(height-1); if((height - 1) % 2 == 1) Pole = Neighbor((TowerHeight - height + 1) %2); moveDisk(height); Pole = Neighbor((TowerHeight - height + 1) %2); hanoi(height-1); } }
And if we move the assignments of Pole to procedure moveDisk (the first assignment before the procedures prints anything and the seconde after the printing is done), we get the following procedure:
static void hanoi(int height) { if (height <> 0) { hanoi(height-1); moveDisk(height); hanoi(height-1); } }
Now, we must remove recursion. Applying the techniques of section "Removing Recursion", it is a straightforward exercise to produce a non-recursive version of the previous procedure and the reader is urged to apply what he/she has already learned! The following procedure is derived by transformations from the stack based equivalent procedure created from the recursive one:
static void hanoi(int height) { int[] HeightStack = new int[height]; int SP = -1; while (height > 0) { SP++; HeightStack[SP] = height; height--; } while (SP >= 0) { height = HeightStack[SP]; SP--; moveDisk(height); height--; while (height > 0) { SP++; HeightStack[SP] = height; height--; } } }
It is not that difficult to replace the stack in the previous procedure by stack, which in turn can be replaced by an integer. Here comes the set oriented version in pseudo-Java:
static void hanoi(int height) { integerSet HS = {1..height}; while ( HS != emptySet ) { height = 1; while (! (height in HS)) height++; HS = HS setDiff {height}; moveDisk(height); HS = HS setUnion {1..height}; } }
where setDiff and setUnion denote set difference and union respectively. Now, we can replace the stack and the stack operations with an integer and operations on integers. First we observe that there is a one-to-one correspondence between subsets of the set {1..k} and the integers 1..2^{k}-1. Secondly, we have the following equivalences:
Sets | Integers |
integerSet s; | unsigned integer s; |
s = [1..k]; | s = (int)Math.pow(2, k)-1; |
s != emptySet; | s != 0; |
!(k in s ) | s % (int)Math.pow(2, k) == 0 |
s setMinus {k} | s - (int)Math.pow(2, k-1) |
s setUnion {1..k-1} | s + (int)Math.pow(2, k-1) -1 |
Thus we can transform the set-oriented version:
static void hanoi(int height) { int s = (int)Math.pow(2, height) - 1; while (s != 0) { height = 1; while (s % (int)Math.pow(2, height) == 0) height++; s -= (int)Math.pow(2, height - 1); moveDisk(height); s += (int)Math.pow(2, height - 1) - 1; } }
Now, let's simplify further the above procedure:
static void hanoi(int height) { int s, power2Height; for (s = (int)Math.pow(2, height) - 1; s>0; s--) { height = 1; power2Height = 2; while (s % power2Height == 0) { height++; power2Height *= 2; } moveDisk(height); } }
So, after many transformations of the original recursive solution, Rohl managed to present a purely iterative solution, and consequently to partially respond to Hayes's challenge.