An optimal solution
to the Towers of Hanoi Puzzle

Universidad Autónoma de Manizales

Carlos Rueda
April, 1997

A non-recursive, constant space complexity solution for a generalization of the Tower of Hanoi problem is described. This generalization allows arbitrary initial and final disk configurations. The number of moves achieved is the minimum possible. Some aspects about the mathematical-computational relationship of the problem are briefly discused and an informal demonstration of the proposed algorithm correctness and optimality is presented.

1. Introduction

The Tower of Hanoi problem (invented by Edouard Lucas in 1883) is classical in computer science being a must example when studying recursion. The relationship between the mathematical function that says how many moves are required and the solution algorithm that says how the moves are to be performed is a question that arises there. After briefly describing the original problem and its classical recursive solution, a non-recursive, O(1) memory complexity algorithm that solves the less-restricted problem that allows arbitrary initial and final positions is presented. We refer to this generalization with the plural The Towers of Hanoi. Finally, an intuitive demonstration of the algorithm validity is described and the problem of finding a formal demonstration is left open.

2. The original problem: The Tower of Hanoi

There are N different sized disks stacked on 3 places, A, B and C. Initially the N disks form a single tower on A. Denoting each disk with a number we have:

The problem is to move the tower from A to C with the help of B according to the following rules:

If we write hanoi(N, source, dest, aux) to denote: "pass N disks from source to dest using aux", then the problem is:

Rule (b) implies that for the greatest disk to be moved to C, the smaller N - 1 disks must be first placed on B; thus, to pass disk N from A to C one move will suffice. To complete the task, it remains to pass the N - 1 disks from B to C. Clearly, this is a recursive strategy that can be written as follows:

The total number of required moves can be easily formulated from the algorithm structure:

whose closed form is h(N) = 2^N - 1. Obviously, if the time complexity is measured in number of moves, this solution is O(2^N). Note also that, as a consecuence of recursion nesting, the space complexity is O(N).

3. The generalized problem: The Towers of Hanoi

Following the original Lucas rules, we will allow arbitrary initial and final configurations, that is, with more than one tower. For instance, with N = 6 disks we could have:

                  2                                1
      1           4                          4     2
      3     5     6                    6     5     3
    ----- ----- -----                ----- ----- -----
      A     B     C                    A     B     C
    Initial state                      Final state
 
First we prove by induction that this version is always solvable. Let N be the number of disks involved. For N = 1 clearly there exists a solution. With N > 1, if the greatest disk N is already in its final position, there exists a solution for N-1 by induction; otherwise, the smaller N - 1 disks can be moved by induction to the alternative place between the current place of disk N and its final place, then the disk N is moved to its final position and for the remaining N-1 disks there is a solution again by induction.

Fine, but this is a losely constructive demonstration especially if we are looking for a non-recursive strategy. The non-recursive algorithm presented below is the result of a pencil-and-paper analysis.

Also it is easy to demonstrate that the number of moves is not greater than 2^N-1. If the greatest N does not have to be moved, 2^N-1-1 moves will suffice (by induction); otherwise, (2^N-1-1) + 1 + (2^N-1-1) moves will suffice (again by induction) ¹.
 

4. The algorithm

Letting current and final be the initial and final states, the algorithm is as follows:

    solve ( current, final )
    {
 1      let max be the number of disks
 2      let dest be the final place of max
 3      let disk = max
        repeat
 4          while disk > 0 do
 5              if disk is already on dest,
 6              or, moving it succeeds then
 7                  if disk = max then
 8                      decrement max by 1
 9                      if max = 0 then
10                          return    // done
                        end if
11                      let dest be the final place of max
                    end if
                else
12                  let dest be the alternative place between dest and
                    the current place of disk
                end if
13              decrement disk by 1
            end while
14          let p and q be the places different of dest
15          let disk be the smaller of the disks on top of p and q
16          let dest be the place between p and q with greater disk on top
        end repeat
    }

Does it work?

The following comments help to explain the algorithm and justify, intuitively at least, its correctness and optimality.

• max
• is the number of the current greatest disk being solved. When this value reaches zero, we are done (lines 9-10).
• disk
• denotes the greatest disk from a portion of disks. When max cannot be moved directly, disk begins to take smaller values until it (i.e., disk) can be moved. Later it will get the value 1 and the disk can clearly be moved.
• dest
• is the place towards which disk must be moved. When the move is not possible,  dest becomes the alternative place (line 12).
• When disk gets zero, the final section (lines 14-16) updates disk and dest according to the places different of dest. Note that this place is where disk 1 was just placed. Therefore, there is not but one alternative to the next move if disk 1 is not moved again: simply move the smaller disk onto the greater (an empty place is supossed to give a special top value greater than any actual disk). Once disk and dest are updated the while loop is performed again and the corresponding move will succeed (line 6). (Line 6 checks if the move is possible and, if so, performes it.)

Seeing is believing. In this applet you can design the configurations as you like and see the algorithm at work.

Note that the space complexity of the solution is O(1): only three integer variables are used (max, dest and disk). Of course, the space complexity of the towers representation will be greater (O(N) in principle) since each disk position must be known (lines 2, 5, 6, 11).

5. Conclusions and further work

This paper has shown a rather simple but elegant algorithm -in the author's hope- for solving optimally (with the minimum number of moves) the Towers of Hanoi problem in which the initial and final states can be arbitrarly configurated. An intuitive justification of its correctness and optimality has been exposed but a completely formal demonstration is in order. We are working currently on this matter (the designing of a recursive algorithm could surely provide an useful insight into the procedure to help find this demonstration). The author will be pleased to receive any help.

I acknowledge Gonzalo Medina for his help to improve this exposition.

References

[1] Graham, R. L., Knuth, D., Patashnik, O. Concrete Mathematics: A Foundation for Computer Science. Second Edition. Addison-Wesley. 1994.