Now, each recursive call is replaced by a set of instructions which do the following:
These steps are sufficient to remove all recursive calls from a subroutine. Finally, we need to append code just after the last executable statement to do the following:
If we need to move disk 1, we have two choices, since we never violate the rule of having to place a smaller on a larger disk. Disk 1 is the smallest. We have to remember where 1 was before, and if we know where 1 is now, there is only possibility left. Here we use the observation that all disks move in cycles. The cycle once started by a disk is maintained until completion.
If we move a disk different from 1, then we know that all such moves are dictated by the position of disk 1, since we cannot move on top of it. Because of this restriction and since we may not leave a disk at the old place, there is again only one choice left. So, to calculate where to move we use the following formula, based one the position of disk 1 and the disk currently to be moved.
Let us now define the level of a node of this tree to be 1 if the node is a leaf, 2 if it is the parent of a leaf, etc. Moreover, let Sn be the sequence of the levels of the nodes encountered during the traversal. It follows that Sn has 2n-1 elements and satisfies:
| Number | Binary representation | Position of rightmost one |
|
|
|
|
|
|
|
|
|
|
|
|
For interior nodes on odd-numbered levels, the same line of reasoning shows
the swap to be "X" if the previous node was on an even level, and "XY"
("X" followed by "Y") otherwise. The combination of the previous ideas leads
to program hanoiD.
He starts the program transformation by removing all but the first parameter
of the recursive solution. In his recursive version the pegs are represented
by the integers 1 (fromPole), 2 (toPole), and 3
(withPole). According to this scheme we can eliminate
withPole, simply because
It is interesting to note that at each recursive
call we decrease the
height of the tower by one and we invert the direction. Thus, the
direction is redutant since it can be defined by the parity of the current
height (k). Consequently, we don't need function Opposite
and so the definition of the hanoi procedure is
simplified .
We can go a step further and eliminate the second argument
too. How? Simply by observing that a disk always moves at the same direction,
and that odd-numbered disks move in one direction while the even-numbered
disks move in the opposite direction. The elimination of the second argument
is based on the following observation:
Now,
we turn our attention to the complete removal of recursion. By using the
techniques of section "Removing Recursion",
we can easily remove the recursive calls. First, we move the assignments
to the global variable that substituted the second argument to the
procedure that prints the moves. Next, we design our stack-based solution
based on principles that have been exposed previously. The resulting
procedure can be further simplified by replacing the stack with a set,
which in turn can be replaced by an integer! This way we get a very simple
solution.
Solutions that resemble the solution of this section have been proposed
by Walsh [7] in and Buneman and Levy in
[8].
A Response to a Challenge by Hayes
The solution(s) presented in this section are a response of
J.S. Rohl ([5])
to a challenge thrown down by P. J. Hayes ([6]):
It would be a very nontrivial exercise to convert (the recursive version)
to (the non-recursive version), let alone convert it mechanically. In fact...
I hereby offer it as a challenge to optimistic optimizers, and to those
who make it their business to prove that equivalent programs area equivalent.
Rohl has derived some very interesting non-recursive solutions to the
problem by eliminating the recursion from the recursive solution (if you
haven't reviewed the recursive solution, now
it's time to do it).
In order to move a tower of height k from peg fromPole to its
neighbor in direction dir, we must first move the tower of height
k-1
to to its neighbor in the
These observations lead to program hanoiE1.
Any parameter called by value can be replaced by a global variable, provided
there exists an inverse for each expression used as an actual parameter for
it.
So, we have to first identify the expression and then to discover its inverse.
Then we we create a global variable and assign to it its value before
a recursive call and reassign to it its original value after the recursive
call by using the inverse expression. This remarks lead us in an even more
simplified solution.
The ``Radix 6 Number'' Solution
Gault and Clint in [9] present a solution that
computes the solution in n steps instead of 2n-1 steps, but still
this solution needs a storage of length 2n-1. The solution is based
on the observation that there are six different possible moves and so a
sequence of disk transfers may be encoded as number of radix 6. Each digit
of this number corresponds to a single move. The following tables present the
encoding:
Clockwise moves
Code
Anticlockwise moves
Code
Using bitwise logical and shift operators
Surprisingly if we treat a particular move as a bitstring, then we can
solve the problem very easy. The two solutions I am presenting here had
been brought to my attention by Adam Moorhouse and Glenn C. Rhoads.
The kernel of the solution by Glenn C. Rhoads is just the following loop:
for (int x=1; x < (1 << n); x++)
{
FromPole = (x&x-1)%3;
ToPole = ((x|x-1)+1)%3;
moveDisk(FromPole,ToPole);
}
The expression 1 << n is actually equal to 2n. The
operators & and | perform the bitwise AND and the bitwise
inlcusive OR operations, respectively. The kernel of the solution by
Adam Moorhouse is the following loop:
for (int move = 1; move < (1 << height) ; move++)
{
int piece = (int)( Math.log( move ^ ( move - 1 )) / log2 ) + 1;
int fromPole = ( move >> piece ) * ( piece % 2 == 0 ? 1 : -1 ) % 3;
int toPole = ( from + (piece % 2 == 0 ? 1 : -1)) % 3;
fromPole = (from +3) % 3;
toPole = (to + 3) % 3;
moveDisk(fromPole, toPole);
}
The operator ^ performs the bitwise exlusive OR operation.
You can now read more about these solutions.
References