Back to the main page.

A Hanoi Tower

The Towers of Hanoi
Apostolos Syropoulos

1. Introduction

I do not know of any other puzzle, that has attracted more the attention of so many programmers around the globe, than the classical “Towers of Hanoi” puzzle. But why is it so popular? Unfortunately, I cannot speak of any other person but myself. Back in 1984, a Lecturer of the Department of Mathematics of the University of Ioannina, Greece, gave me a copy of an article about the Lisp programming language. In that article, the author in order to present the capabilities of the language used the “Towers of Hanoi” puzzle. This was a big surprise for me, bec ause I always had the wrong impression that computers are good only in performing arithmetic operations. After that I tried to learn more about the puzzle. This search, in the long term, gave me the opportunity to learn about many things I wasn't aware of. But, who invented this puzzle and what is it about? The “Towers of Hanoi” puzzle was invented by François Édouard Anatole Lucas, a French mathematician, around 1883. The puzzle can be stated as follows: There are 3 needles and a tower of disks on the first one, with the smaller on the top and the bigger on the bottom. The purpose of the puzzle is to move the whole tower from the first needle to the second, by moving only one disk every time and by observing not to put a bigger disk atop of a smaller one. The legend that is popularly attached to it appeared in, among others, the “Metamagical Themas” column of the Scientific American magazine [1]:

In the great temple of Brahma in Benares, on a brass plate under the dome that marks the center of the world, there are 64 disks of pure gold that the priests carry one at a time between these diamond needles according to Brahma's immutable law: No disk may be placed on a smaller disk. In the begging of the world all 64 disks formed the Tower of Brahma on one needle. Now, however, the process of transfer of the tower from one needle to another is in mid course. When the last disk is finally in place, once again forming the Tower of Brahma but on a different needle, then will come the end of the world and all will turn to dust.

There are many solutions to the “Towers of Hanoi” problem and this document is an effort to present all of them. Here we describe the various solutions and we present their implementation in the Java programming language. This work should by no means considered original, but rather an editorial work.

2. Solving the Problem

The “Towers of Hanoi” problem can be solved by a simple problem-reduction approach. One way of reducing the original “Towers of Hanoi” problem, i.e., that of moving a tower of n disks from pole A to pole B by using pole C, to a set of of simpler problems involves the following chain of reasoning:

  1. In order to move all of the disks to pole B we must certainly move the biggest disk there, and pole B must be empty just prior to moving the biggest disk to it.
  2. Now looking at the initial configuration, we can't move the biggest disk anywhere until all other disks are first removed. Furthermore, the other disks had better not be moved to pole B since then we would not be able to move the biggest disk there. Therefore we should first move all other disks to pole C.
  3. Then we can complete the key step of moving the biggest disk from pole A to pole B and go on to solve the problem

In this way we have reduced the problem of moving a tower to the one of moving a tower with height one less and that of moving the biggest disk. This solution can be most effectively rendered as a recursive procedure, i.e., a procedure that is defined in terms of it self. Program hanoiA implements the recursive solution suggested by the above solution.

3. Removing Recursion

Every recursive subroutine can be transformed into a non-recursive one by a series of simple steps. The necessary steps are described in many good text books on Data Structures, e.g., [2]. The transformation assumes that our programming language supports gotos. In case it doesn't (as it is usually the case today), we can transform it to some pseudo-language and then simply replace the unconditional jumps with iterative constructs, e.g., while loops. The following rules assume that the labels 1, 2,..., k are not used in the recursive subroutine. Moreover, k is one more than the number recursive calls in a given subroutine.

  1. At the beginning of the subroutine, code is inserted which declares stacks associated with each formal parameter, each local variable, and the return address for each recursive call. Initially all stacks are empty.
  2. The label 1 is attached to the first executable program statement.
  3. If the subroutine is a function, i.e., returns some value, then we must replace all return statements with assignment statements, i.e., we introduce a fresh variable, say z, which has the same type as that of the function, and replace each return e statement with a z=e statement.
  4. Now, each recursive call is replaced by a set of instructions which do the following:

  5. Store the values of all parameters and local variables in their respective stacks. The stack pointer is the same for all stacks.
  6. Create the i-the label, i, and store i in the address stack. The value i of this label will be used as the return address. This label is placed in the subroutine as described in rule 8.
  7. Evaluate the arguments of this call (they may be expressions) and assign these values to the appropriate formal parameters.
  8. Insert an unconditional branch to the beginning of the subroutine.
  9. If this is a procedure, add the label created above to the statement immediately following the unconditional branch. If this is a function then follow the unconditional branch by code to use the value of the variable z in the same way a return statement was handled earlier. The first statement of this code is given the label that was created above.

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:

  1. If the recursion stacks are empty, then return the value of z, i.e., return z, in case this is a function, or else simply return.
  2. If the stacks are not empty, then restore the value of all parameters and of all local variables. These are at the top of the each stack. Use the return label from the corresponding stack and execute a branch to this label. This can be done using a switch statement.

The above rules can be used to transform the recursive solution into an iterative one. Program hanoiB has all the details.

4. The Fourth Grade Solution

Let m be a natural binary number with at most n digits, then m lies in the range 0..2n-1. Moreover, let m have exactly n digits, with the rightmost digits having index 1 and the leftmost having index n. If we increment m by one, then exactly one digit changes from '0' to '1'. Furthermore, it can be proved that we need 2n-1 moves to solve the Towers of Hanoi puzzle, for a tower of height n. The combination of these remarks are the idea behind the Fourth Grade Solution (FGS) [3]: if the number m is set initially to zero, each time we increment it by one, the index of the digit that changes from '0' to '1' corresponds to the disk that has to be moved. This means that we use the successive values of m to determine which disk to move. Now we must determine where to move each disk. The description provided in [3], slightly edited, follows:

Disk 1 is initially placed on pole B for odd n and pole C for even n.
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.

to_position := 6 - where_1_is - where_disk_is to_position := 6 - Hold[1] - Hold[Disk]

Program hanoiC has all the details.

5. The French Solution

The French Solution [4], called so because its inventors are French, is essentially equivalent to the FGS. The solution is based on the observation that for a recursive procedure a tree can be associated. In the case of the recursive solution of the puzzle, the associated tree is a binary one. Each node of this tree has a label of the form x->y, which denotes a move of a disk from pole x to pole y. The values of x and y depend on which recursive call they correspond, i.e., the first recursive call swaps arguments withPole and toPole and so the label of the root is A->B (the second recursive call swaps arguments fromPole with withPole). Furthermore, we label each edge of the tree "Y" or "X" depending on which of the of the swaps takes place on the destination of the edge. An in-order traversal of the tree solves the puzzle, i.e., execution of the procedure can be viewed as in-order traversal of the tree.

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:

Thus S1 = <1>, S2 = <1 2 1>, S3 = <1 2 1 3 1 2 1>, etc. An interesting remark is that the sequence Sn and Cn are identical, where C is the sequence whose n-th element Cn is the sequence of indexes (counted from the rightmost position) of the rightmost ones in the binary representations of the numbers 1, 2, 3, ..., 2n-1. That is, C2 = <1 2 1> denotes the position of the rightmost one of the binary representation of the numbers 1, 2, and 3, as can be verified from the following table:

Number Binary representation Position of rightmost one
111
2102
3121

Coming back to the binary tree representing the execution of the procedure, it follows from the definition of the procedure that, during the traversal, leaves and interior nodes are alternatively visited. Let's consider what happens when a node E with an even-umbered level is visited and try to understand the way a program can reach such a node. E may only be an interior node; thus the preceding one was a leaf, say L. If L is a left child, then E is its parent and the swap to perform is a "Y", i.e., swap arguments withPole and toPole; otherwise, to go from L to E, a program has to go up the tree x times, performing x swaps of the "X" type, i.e., swaps arguments fromPole with withPole, then up one "Y". But E is at an even level, L is at an odd level, so the difference between their levels in the tree, which is x+1, must be odd; thus x is even, which means that the "X" swaps cancel out and that has to be done is one "Y" swap.

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.

6. 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).

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 fromPole+toPole+withPole=6 Now it's the turn of parameter toPole to be eliminated. If we think the three pegs in a triangular arrangement, then we can replace toPole by its direction, i.e., clockwise or anticlockwise from fromPole. This means that we have to modify procedures moveDisk and hanoi, so that they can calculate the destination of the move from fromPole and dir. Under these considerations the solution is rephrased as follows

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 opposite direction; then we move the bottom disk to the its neighbor in direction dir, and finally we move the tower of height k-1 in the opposite direction.

These observations lead to program hanoiE1.

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:

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.

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].

7. 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
From A to B 16
From C to A 26
From B to C 36
Anticlockwise moves Code
From B to A 46
From A to C 56
From C to B 06

Now, the solution can be expresses by the simple formula:

H(n,x,y) = H(n-1,x,z) ++ H(1,x,y) ++ H(n-1,z,y)

where H(1,x,y) is the code for the move from pole x to pole y and ++ the string concatenation operator. The authors observed that it is possible to define the operator ++ as follows:

c1 ++ c2 = c1*106n + c2,

where c2 represent a sequence of moves, i.e., a number of radix 6. You can now read more about this solution.

8. 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

  1. R. Douglas Hofstadter. Metamagical themas. Scientific American, 248(2):16-22, March 1983.
  2. Ellis Horowitz and Sartaj Sahni. Fundamentals of Data Structures in Pascal. Computer Science Press, Rockville, MD, USA, 1984.
  3. Herbert Mayer and Don Perkins. Towers of Hanoi Revisited. SIGPLAN Notices, 19(2):80-84, February 1984.
  4. Bertrand Meyer. A Note On Iterative Hanoi. SIGPLAN Notices, 19(12), December 1984.
  5. J. S. Rohl. Towers of Hanoi: The Derivation of Some Iterative Versions. The Computer Journal, 30(1), 70-76, 1987.
  6. P. J. Hayes. A note on the Towers of Hanoi Problem. The Computer Journal, 20(3), 282-285, 1977.
  7. T. R. Walsh. The Towers of Hanoi Revisited: Moving the rings by counting the moves. Information Processing Letters, 15(2), p-p, 1982.
  8. P. Buneman and L. Levy. The Towers of Hanoi Problem. Information Processing Letters, 10(4,5), p-p, 1980.
  9. D.Gault and M. Clint. A Fast Algorithm for the Towers of Hanoi Problem. The Computer Journal, 30(4), 376-378, 1987.

Back to the main page.