Program Development by Stepwise Refinement (1971)

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. Obviously B 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:

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. This technique is called backtracking and may generally be characterized by the program:

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.

Source: sunnyday.mit.edu