Universidad Autónoma de Manizales
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.
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.
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:
1 1The problem is to move the tower from A to C with the help of B according to the following rules:
(a) Only one disk can be moved at a time;
(b) No disk can rest onto a smaller disk.
If we write hanoi(N, source, dest, aux) to denote: "pass N disks from source to dest using aux", then the problem is:
hanoi(N, A, C, B)
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:
hanoi ( N, source, dest, aux )
{
if N > 0 then
hanoi(N - 1, source, aux, dest)
move disk N from source to dest
hanoi(N - 1, aux, dest, source)
end if
}
The total number of required moves can be easily formulated from the algorithm structure:
h(N) = h(N - 1) + 1 + h(N - 1)
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).
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) ^{1}.
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.
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).
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.
[1] Graham, R. L., Knuth, D., Patashnik, O. Concrete Mathematics: A Foundation for Computer Science. Second Edition. Addison-Wesley. 1994.