A)
r(x)}.
Obviously Br 
A.
Instead of generating elements of A, only elements of
B are produced and tested on condition q
instead of
p.
Suitable the following requirements:
This is a digitized copy derived from an ACM copyrighted work. It is not guaranteed to be an accurate copy of the author's original work.
Key Words and Phrases: education in programming, programming techniques, stepwise program construction
CR Categories: 1.50, 4.0
This paper deals with a single example chosen with these two purposes in mind. Some well-known techniques are briefly demonstrated and motivated (strategy of preselection, stepwise construction of trial solutions, introduction of auxiliary data, recursion), and the program is gradually developed in a sequence of refinement steps.
In each step, one or several instructions of the given program are decomposed into more detailed instructions. This successive decomposition or refinement of specifications terminates when all instructions are expressed in terms of an underlying computer or programming language, and must therefore be guided by the facilities available on that computer or language. The result of the execution of a program is expressed in terms of data, and it may be necessary to introduce further data for communication between the obtained subtasks or instructions. As tasks are refined, so the data may have to be refined, decomposed, or structured, and it is natural to refine program and data specifications in parallel.
Every refinement step implies some design decisions. It is important that these decision be made explicit, and that the programmer be aware of the underlying criteria and of the existence of alternative solutions. The possible solutions to a given problem emerge as the leaves of a tree, each node representing a point of deliberation and decision. Subtrees may be considered as families of solutions with certain common characteristics and structures. The notion of such a tree may be particularly helpful in the situation of changing purpose and environment to which a program may sometime have to be adapted.
A guideline in the process of stepwise refinement should be the principle to decompose decisions as much as possible, to untangle aspects which are only seemingly interdependent, and to defer those decisions which concern details of representation as long as possible. This ferent environments (languages and computers), where different representations may be required.
The chosen sample problem is formulated at the beginning of section 3. The reader is strongly urged to try to find a solution by himself before embarking on the paper which-of course-presents only one of many possible solutions.
repeat (statement sequence)
until (boolean expression)
is introduced, meaning that the statement sequence is to be repeated until the boolean expression has obtained the value true.
This problem is characteristic for the rather frequent situation where an analytical solution is not known, and where one has to resort to the method of trial and error. Typically, there exists a set A of candidates for solutions, among which one is to be selected which satisfies a certain condition p. Thus a solution is characterized as an x such that (x belongs to A) and p(x).
A straightforward program to find a solution is:
repeat Generate the next element of A and call it x
until p(x) V (no more elements in A);
if p(x) then x = solution
The difficulty with this sort of problem usually is the
sheer size of A, which forbids an exhaustive generation
of candidates on the grounds of efficiency
considerations. In the present example, A consists of
64!/(56! X 8!) = 2^32 elements (board
configurations). Under the assumption that generation and
test of each configuration consumes 100 microseconds, it
would roughly take 7 hours to find a solution. It is
obviously necessary to invent a "shortcut," a method
which eliminates a large number of "obviously"
disqualified contenders. This strategy of preselection is
characterized as follows: Find a representation
of p in the form p = q and r.
Then let Br =
{x | (x A)
r(x)}.
Obviously Br
A.
Instead of generating elements of A, only elements of
B are produced and tested on condition q
instead of
p.
Suitable the following requirements:
The corresponding program then is:
repeat Generate the next element of B and call it x until q(x) V (no more elements in B); if q(x) then x = solution
A suitable condition r in the 8-queens problem is the rule that in every column of the board there must be exactly one queen. Condition q then merely specifies that there be at most one queen in every row and in every diagonal, which is evidently somewhat easier to test than p. The set Br, (configurations with one queen in every column) contains "only" 8^8 = 2^24 elements. They are generated by restricting the movement of queens to columns. Thus all of the above conditions are satisfied.
Assuming again a time of 100 ,us for the generation and test of a potential solution, finding a solution would now consume only 100 seconds. Having a powerful computer at one's disposal, one might easily be content with this gain in performance. If one is less fortunate and is forced to, say, solve the problem by hall (it, it would take 280 hours of generating and testing configurations at the rate of one per second. In this case it might pay to spend some time finding further shortcuts. Instead of applying the same method as before, another one is advocated here which is characterized as follows: Find a representation of trial solutions x of the form {x1, x2, ··· , xn}, such that every trial solution can be generated in steps which produce [x1], [x1, x2], [x1, x2, ··· , xn] respectively. The decomposition must be such that:
q(x1 ··· xj) for all j < n.
Thus a full solution can never be obtained by extending a partial trial solution which does not satisfy the predicate q. On the other hand, however, a partial trial solution satisfying q may not be extensible into a complete solution. This method of stepwise construction of trial solutions therefore requires that trial solutions failing at step j may have to be "shortened" again in order to try different extensions. This technique is called backtracking and may generally be characterized by the program:
j := 1;
repeat trystep j;
if successful then advance else regress
until (j < 1) V (j > n)
In the 8-queens example, a solution can be constructed by positioning queens in successive columns starting with column 1 and adding a queen in the next column in each step. Obviously, a partial configuration not satisfying the mutual nonaggression condition may never be extended by this method into a full solution. Also, since during the jth step only j queens have to be considered and tested for mutual nonaggression, finding a partial solution at step j requires less effort of inspeclion than finding a complete solution under the condition that all 8 queens are on the board all the time. Both stated criteria are therefore satisfies by the decomposition in which step j consists of finding a safe position for the queen in the jth column.
The program subsequently to be developed is based on this method; it generates and tests 876 partial configurations before finding a complete solution. Assuming again that each generation and test (which is now more easily accomplished than before) consumes one second, the solution is found in 15 minutes, and with the computer taking 100 microseconds per step, in 0.09 seconds.
variable board, pointer, safe;
considerfirstcolumn;
repeat trycolunm;
if safe then
begin setqueen; considernextcolumn
end else regress
until lastcoldone V regressouttofirstcol
This program is composed of a set of more primitive instructions (or procedures) whose actions may be described as follows:
considerthiscolumn. The problem essentially consists of inspecting the safely of squares. A pointer variable designates the currently inspected square. The column in which this square lies is called the currently inspected column. This procedure initializes the pointer to denote the first column.
trycolumun. Starting at the current square of inspection in the currently considered column, move down the column until a safe square is found, in which case the boolean variable safe is set to true, or until the last square is reached and is also unsafe, in which case the variable safe is set to false.
setqueen. A queen is positioned into the last inspected square.
considernextcolumn. Advance to the next column and initialize its pointer or inspeclion.
regress. Regress to a column where it is possible to move the positioned queen rurther down, and remove the queens positionted in the columns over which regression takes place. (Note that we may have to regress over at most two columns. Why?)
The next step of program development was chosen to refine the descriptions of the instructions trycolumn and regress as follows:
procedure trycolumn; repeat advancepointer; testsquare until safe V lastsquare
procedure regress;
begin reconsiderpriorcolumn
if - regressouttofirstcol then
begin removequeen;
if lastsquare then
begin reconsiderpriorcolumn;
if not regressouttofirstcol then
removequeen
end
end
end
The program is expressed in terms of the instructions:
considerfirstcolumn
cibsidernextcolumn
reconsiderpriorcolumn
advancepointer
testsquare (sets the variable
setqueen
removequeen
and of the predicates: lastsquare lastcoldone regressouttofirstcol
In order to refine these instructions and predicates further in the direction of instructions and predicates available in common programming languages, it becomes necessary to express them in terms of data representable in those languages. A decision on how to represent the relevant facts in terms of data can therefore no longer be postponed. First priority in decision making is given to the problem of how to represent the positions of the queens and of the square being currently inspected.
The most straightforward solution (i.e. the one most closely renecting a wooden chessboard occupied by marble pieces) is to introduce a Boolean square matrix with B[i, j] = true denoting that square (i, j) is occupied. The success of an algorithm, however, depends almost always on a suitable choice of its data representation in the light of the ease in which this representation allows the necessary operations to be expressed. Apart from this, consideration regarding storage requirements may be of prime importance (although hardly in this case). A common dilliculty in program design lics in the unfortullale fact that at the stage where decisions about data representations have to be made, it often is still difficult to foresee the details of the necessary instructions operating on the data, and vften quite impossible to estimate the advantages of one possible representation over another. In general, it is therefore advisable to delay decisions about data representation as long as possible (but not until it becomes obvious that no realizable solution will suit the chosen algorithm).
In the problem presented here, it is fairly evident even at this stage that the following choice is more suitable than a Boolean matrix in terms of simplicity of later instructions as well as of storage economy.
j is the index of the currently inspected column; (xj, j) is the coordinate of the last inspected square; and the position of the queen in column k < j is given by the coordinate pair (xk, k) of the board. Now the variable declarations for pointer and board are refined into:
integer j (0 <= j <= 9) integer array x[1:8] (0 <= xi <= 8)conditions and predicates are expressed as: procedure considerfirstcolumn; begin j := 1; x[1] := 0 end
procedure considernextcolumn; begin j := j + 1; x[j] = 0 end
procedure reconsiderpriorcolumn; j := j - 1
procedure advancepointer; x[j] := x[j] + 1
Boolean procedure EM>lastsquare; lastsquare := x[j] = 8;
Boolean procedure lastcoldone; lastcoldone := j > 8
Boolean procedure regressouttofirstcol := j < 1
At this stage, the program is expressed in terms of the instructions:
testsquare
setqueen
removequeen
As a matter of fact, the instructions setqueen and
removequeen may be regarded as vacuous, if we decide
that the procedure testsquare
is to determine the
value of the variable
The introduction of V is advantageous (apart from considerations of storage economy), if
n(k - 1)u > mu or (n/m)(k - 1) > (v/u),
i.e. if the gain is greater than the loss in computation units.
A most straightforward solution to obtain a simple version of testsquare is to introduce a Boolean matrix B such that B[i,j] = true signifies that square (i,j) recomputation whenever a new queen is removed is prohibitive (why?) and will more than outweigh the gain.
The realization that the relevant condition for safety of a square is that the square must lie neither in a row nor hl a diagonal already occupied by another queen, leads to a much more economic choice of V. We introduce noolean arrays a, b, c with the meanings:
ak = true : no queen is positioncd in row k
ck = true : no queen is positioned in the \-diagonal k
The choice of the index ranges of these arrays is made in view of the fact that squares with equal sum of their coordinates lie on the same /-diagonal, and those with equal difference lie on the same \-diagonal. With row and column indices from I to 8, we obtain:
Boolean array a[1:8],b[2:16],c[-7:7]
Upon every introduction of :auxiliary data, care has to he taken of their correct initialization. Since our algorithm starts with an empty chessboard, this fact must be represented by initially assigning the value true to all components of the arrays a,b, and c. We can now write:
procedure testsquare;
safe := a[x[j]]
The correctness of the latter procedure is based on the fact that each queen currently on the board had been positioned on a safe square, and that all queens positioned after the one to he removed now had already been removed. Thus the square to be vacated becomes safe again.
A critical examination of the program obtained so far reveals that the variable x[j] occurs very often, and in particular at those places of the program which are also executed most often. Moreover, examination of x[j] occurs much more frequenlly than reassignment of values to j. As a consequence, the principle of introduction of new auxiliary data can again be applied to increase efficiency: a new variable
integer i
is used to represent the value so far denoted by x[j] Consequently x[j] = i must always be executed before j is increased, and i: = x[j] after j is decreased. This final step of program development leads to the reformulation of some of the above procedures as follows:
procedure testsquare; safe := a[i]
The final program, using the procedures
testsquare
setqueen
regress
removequeen
and with the other procedures directly substituted, now has the form
j := 1; i := 0; repeat repeat i := i + 1; testsquare until safe(i = 8); if safe then begin setqueen; x[j] := i; j := j + 1; i := O end else regress until (j > 8)
It is noteworthy that this program still displays the structure of the version designed in the first step. Naturally other, equally valid solutions can be suggested and be developed by the same method of stepwise program refinement. It is particularly essential to demonstrate this fact to students. One alternative solution was suggested to the author by E. W. Dijkstra. it is based on the view that the problem consists of a stepwise extension of the board by one column containing a safely positioned queen, starting with a null-board and terminating with 8 columns. The process of extending the board is formulated as a procedure, and the natural method to obtain a complete board is by recursion of this procedure. It can easily be composed of the same set of more primitive instructions which were used in the first solution.
procedure trycolumn
begin integer i; i := 0;
repeat i := i + 1; testsquare;
if safe then
begin setqueen; x[j] := i;
if j < 8 then trycolumn(j+1);
if not safe then removequeen
end
until safe (i = 8)
end
The program using this procedure then is
Trycolumn(1);
if safe then
PRINT(x) else FAILURE
(Note that due to the introduction of the variable i local to the recursive procedure, every column has its own poinler of inspection i. As a consequence, the procedures
testsquare
setqueen
removequeen
must be declared locally within Trycolumn too, because
they rerer to the i designating the scanned square in the
current column.)
It is the purpose of the subsequent section to demonstrate this advantage in view of a generalization of the original 8-queens problem and its solution through an extension of the program components introduced before.
The generalized problem is formulated as follows:
Find all possible configurations or 8 hostile queens on an 8 X 8 chessboard, such that no queen may be taken by any other queen.
The new problem essentially consists of two parts:
It is evidently necessary to generate and test candidates for solutions in some systematic manner. A common technique is to find an ordering of candidates and a condition to identify the last candidate. If an ordering is found, the solutions can be mapped onto the integers. A condition limiting the numeric values associated with the solutions then yields a criterion for termination of the algorithm, if the chosen method generates solutions strictly in increasing order. It is easy to find orderings of solutions for the present problem. We choose for convenience the mapping
M(x) = 
j = 1 to 8 (xj10^(j-1)
An upper bound for possible solutions is then M(xmax) = 88888888
and the "convenience" lies in the circumstance that our earlier program generating one solution generates the minimum solution which can be regarded as the starting point from which to proceed to the next solution. This is due to the chosen method of testing squares strictly proceeding in increasing order of M(x) starting with 00000000. The method for generating further solutions must now be chosen such that starting with the configuration of a given solution, scanning proceeds in the same order of increasing M, until either the next higher solution is found or the limit is reached.
considerfirstcolumn;
repeat trycolumn;
if safe then
begin setqueen; considernextcolumn;
if lastcoldone then
begin PRlNT(x); regress
end
end else regress
regressouttofirstcol
Indication of a solution being found by printing it now occurs directly at the level of detection, i.e. before leaving the repetition clause. Then the algorithm proceeds to find a next solution whereby a shortcut is used by directly regressing to the prior column; since a solution places one queen in each row, there is no point in further moving the last queen within the eightth column.
The recursive program is extended with even greater ease following the same considerations:
procedure Trycolumn(j);
begin integer i;
(declaralions of procedures testsquare, advancequeen,
setqueen, removequeen, lastsquare)
i := 0;
repeat advancequeen; testsquare;
if safe then
begin setqueen; x[j] := i;
if not lastcoldone then Trycolumn(i + l) else PRlNl'(x);
removequeen
end
until lastsquare
end
The main program starting the algorithm then consists
(apart from initialization of a, b, and c) of the single
statement Trycolumn(1) .
In concluding, it should be noted that both programs represent the same algorithm. Both determine 92 solutions in the same order by testing squares 15720 times. This yields an average of 171 tests per solution; the maximum is 876 test for finding a next solution (the first one), and the minimum is 8. (Both programs coded in the language Pascal were executed by a CDC 6400 computer in less than one second.)
Each refinement implies a number of design decisions based upon a set of design criteria. Among these criteria are efficiency, storage economy, clarity, and regularity of structure. Students must be taught to be conscious of the involved decisions and to critically examine and to reject solutions, sometimes even if they are correct as far as the result is concerned; they must learn to weigh the various aspects of design alternatives in the light of these criteria. In particular, they must be taught to revoke earlier decisions, and to back up, if necessary even to the top. Relatively short sample problems will often suffice to illustrate this important point; it is not necessary to construct an operating system for this purpose.
Acknowledgments. The author gratefully acknowledges the helpful and stimulating influence of many discussions with C.A.R. Hoare and E. W. Dijkstra.
1. Dijkstra, E. W. A constructive approach lo the problem of program correctness. BIT 8 (1968), 174-186.
2. Dijkstra, E. W. Notes on structured programming. EWD 249 Technical U. Eindhoven, The Netherlands, 1969.
3. Naur, P. Programming by action clusters. BIT 9 (1969) 250 - 258.
4. Wirth, N. Programming and programming languages. Proc. Internat. Comput. Symp., Bonn, Germany, May 1970.