EWD316: A Short Introduction to the Art of Programming
by
prof.dr.Edsger W.Dijkstra
August 1971
0. Contents
1. Preface
2. Some Fundamental Notions
3. Programming Languages and their Implementation
4. Variables and relations between their values
5. Programs corresponding to recurrence relations
6. A first example of step-wise program composition
7. The shortest spanning subtree of a graph
8. The towers of Hanoi
9. The problem of eight queens
10. A rearranging routine
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_{0}, we can also solve it for N = N_{0} + 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_{0} + 1, A, B, C)
is the same as that of the successive moves of
movetower (N_{0}, A, C, B)
movedisk (A, C)
movetower (N_{0}, B, A, C) .
In words: first a tower of N_{0} disks is moved from A to B, using C as auxiliary peg, then the N_{0} + 1st disk is moved directly from A to C and finally the tower of N_{0}, 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_{0} smallest disks, the presence of larger disks will not cause violation of the condition of decreasing disk diameter. Moving a one-disk tower (N_{0} = 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_{2}, move_{1}
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_{2}, move_{1}
(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_{2}, move_{1}
In both transformations the lower (i.e. later) k–1 moves have been unaffected.
A move is given by four parameters, say
n | = | number of disks in the tower to be moved |
from | = | number of source peg |
via | = | number of auxiliary peg |
to | = | number of destination peg. |
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
n = | from = | via = | to = | |
k: | N | A | B | C |
is to be replaced by the triple
n' = | from' = | via' = | to' = | |
k'-2 = k: | N-1 | B | A | C |
k'-1 = k+1: | 1 | A | (B) | C |
k' = k-2: | N-1 | A | C | B |
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.
Next chapter: 9. The problem of eight queens