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.
The “Towers of Hanoi” problem can be solved by a simple problemreduction 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:
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.
Every recursive subroutine can be transformed into a nonrecursive 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 pseudolanguage 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.
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:
The above rules can be used to transform the recursive solution into an iterative one. Program hanoiB has all the details.
Let m be a natural binary number with at most n digits, then m lies in the range 0..2^{n}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 2^{n}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.
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 inorder traversal of the tree solves the puzzle, i.e., execution of the procedure can be viewed as inorder 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 S_{n} be the sequence of the levels of the nodes encountered during the traversal. It follows that S_{n} has 2^{n}1 elements and satisfies:
Thus S_{1} = <1>, S_{2} = <1 2 1>, S_{3} = <1 2 1 3 1 2 1>, etc. An interesting remark is that the sequence S_{n} and C_{n} are identical, where C is the sequence whose nth element C_{n} is the sequence of indexes (counted from the rightmost position) of the rightmost ones in the binary representations of the numbers 1, 2, 3, ..., 2^{n}1. That is, C_{2} = <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 
1  1  1 
2  10  2 
3  12  1 
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 evenumbered 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 oddnumbered 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.
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 nonrecursive 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 nonrecursive 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 k1 to to its neighbor in theopposite direction; then we move the bottom disk to the its neighbor in direction dir, and finally we move the tower of height k1 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 oddnumbered disks move in one direction while the evennumbered 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 stackbased 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].
Gault and Clint in [9] present a solution that computes the solution in n steps instead of 2^{n}1 steps, but still this solution needs a storage of length 2^{n}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:


Now, the solution can be expresses by the simple formula:
H(n,x,y) = H(n1,x,z) ++ H(1,x,y) ++ H(n1,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:
c_{1} ++ c_{2} = c_{1}*10_{6}^{n} + c_{2},
where c_{2} represent a sequence of moves, i.e., a number of radix 6. You can now read more about this solution.
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&x1)%3; ToPole = ((xx1)+1)%3; moveDisk(FromPole,ToPole); }
The expression 1 << n is actually equal to 2^{n}. 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.