A Short Introduction to the Art of Programming (EWD 316), Chapter 8

8. The towers of Hanoi

Given three pegs, numbered 1, 2 and 3 and a set of N disks (N > 1) of decreasing diameter and a hole in their centre. At the beginning the N disks are all on peg nr.1 in order of decreasing diameter, i.e. the largest disk is at the bottom, the smallest is at the top side of the first peg. The problem is to move this tower from the first peg to the third one in a number of "moves", where a "move" is moving one disk from the top of a peg to the top of another peg with the restriction that a larger disk may never be placed on top of a smaller one. The second peg may be used as auxiliary "store" for pegs which are "in the way".

Now, if we can solve this game for any two pegs for N = N₀, we can also solve it for N = N₀ + 1 . Call

movetower (m, A, B, C)

the set of moves that transports a tower of m disks from peg A (if necessary via peg B) to peg C. The individual moves are of the form

movedisk(P, Q) .

The set of moves

movetower (N₀ + 1, A, B, C)

is the same as that of the successive moves of

movetower (N₀, A, C, B)
movedisk (A, C)
movetower (N₀, B, A, C) .

In words: first a tower of N₀ disks is moved from A to B, using C as auxiliary peg, then the N₀ + 1st disk is moved directly from A to C and finally the tower of N₀, that has been placed temporarily on peg B is moved to its final destination C, using A as auxiliary peg. As the tower consists of the N₀ smallest disks, the presence of larger disks will not cause violation of the condition of decreasing disk diameter. Moving a one-disk tower (N₀ = 1) presents no difficulty and as a result the puzzle has been solved. The question posed to us, however, is to make a program generating disk moves in the order in which they have to take place.

Note. It is not realistic to demand the execution of this program for large values of N because the total number of moves required = 2^N – 1. Prove this and prove also that the puzzle cannot be solved in a smaller number of moves.

The fact that a move with N > 1 is decomposed into three "smaller" moves, suggests that we keep a list of moves to be done. If the first one to be done is simple, we do it; otherwise we replace it by its decomposition and reconsider our obligations. In both cases, when we have a list of k moves, only the first to be made needs consideration, and while we process it, the remaining k–1 moves remain as standing obligations. This suggests that we introduce

move_k, move_k-1, ... , move₂, move₁

to be done in the order of decreasing subscript, in the order from left to right. If move is simple, it is made, leaving

move_k'=k-1, ... , move₂, move₁

(indicating with k' the new value of k, the length of our list of standing obligations) otherwise move_k, is replaced by three others, leaving

move'_k'=k+2, move'_k'-1=k+1, move'_k'-2=k, move_k'-3=k-1, ... , move₂, move₁

In both transformations the lower (i.e. later) k–1 moves have been unaffected.

A move is given by four parameters, say

We can store these moves in four arrays "integer array n, from, via, to [1:2*N–1]". (Verify that the list of obligations is never longer than 2*N–1 moves.) The non-simple move (with N>1), given in tabular form by

is to be replaced by the triple

in which the top line replaces the original one, while the next two lines are new. (In the middle line the element "via" has been put between brackets, as it is immaterial; the program leaves that value unaffected.)

begin  integer k; integer array n, from, via, to [1:2*N-1]; 
  n[1]:= N; from[1]:=1; via[1]:=2; to[1]:=3; k:=1; 
  repeat if n[k]= 1 then
    begin  movedisk(from[k], to[k]);
           k:= k - 1 
    end
                    else
    begin 
      n[k+2]:= n[k]-1; from[k+2]:= from[k]; via[k+2]:= to[k]; to[k+2]:= via[k];
      n[k+1]:=1; from[k+1]:= from[k]; to[k+1]:= to[k]; 
      n[k]:= n[k+2]; from[k]:= to[k+2]; via[k]:= from[k+2]; to[k]:= via[k+2];
      k := k + 2
    end
  until k = O
end

Remark. In the program we have not described the details of the operation "movedisk(A, B)". If it prints the number pair A, B, the solution will be printed; if the machine is coupled to a mechanical hand which really moves disks, the machine will play the game!

The reader is strongly advised to follow the above program himself for a small value of N (say: 4) so as to see how the value of k goes up and down. The reader is also invited to check carefully the "shunting" of the values N(–1), A, B and C when a non-simple move is decomposed into three simpler ones. This check is a painful process, so painful that everyone who has done it, will only be too willing to admit that the above program is rather ugly. The above program has been included with the aim of making him more appreciative of the elegance of the so-called "recursive solution" which now follows.

begin procedure movetower (integer value m, A, B, C); 
  begin if m = 1 then movedisk (A, C)
                 else
          begin movetower (m-1, A, C, B); 
                movedisk (A, C); 
                movetower (m-1, B, A, C) 
          end 
      end;
      movetower (N,  1,  2,  3) 
end

It introduces an operator named "movetower" with four (integer valued) parameters, moving a tower of length m from A via B to C. In terms of this operator the final program collapses into a single statements as given in the last line, viz. "movetower (N, 1, 2, 3)". All that is given in front of it (lines 2 to 8) describes this operator in terms of a little program, little because the operator is allowed to invoke itself. The definition of the operator (the so-called "procedure body") follows our original analysis of the game exactly. Recursive procedures —i.e. procedures that are allowed to invoke themselves— are such a powerful tool in programming that we shall give some more examples of them.

Remark. Some of the more old-fashioned programming languages do not cater for recursion. Programming cources based on such programming languages often contain many examples that are only difficult because the recursive solution is denied to the student.

Back to top

Next chapter: 9. The problem of eight queens