18 - Eight queens

Summary

We have already learned how Z can be used to describe data structures. Sometimes the solution to a problem is just a data structure that has some particular properties. In that case, the description of the data structure is the central element in the whole specification. A well-known example is the problem of the eight queens.

Many books on programming show how to solve the problem of the eight queens (for example, see Wirth [1976]). Here is the problem statement in English:

Eight queens must be placed on a chessboard so that no queen attacks any others. A chessboard is a square grid with eight columns, or files, and eight rows, or ranks. When a queen is placed on a square, it attacks any other queen that sits on the same rank, file, or diagonals.

Figure 18.1 illustrates one solution to the problem.

This is not a problem of great practical significance, but it does illustrate some common difficulties of prose specifications: They usually turn out to be imprecise and incomplete. The English problem statement is usually considered sufficient because “everybody knows what it means.” When we write real specifications, usually everybody does not know what is needed. When we write the program, we can't appeal to visual impressions and intuitions. Could you explain the eight queens problem to somebody who had never seen a chessboard? What if you had to communicate by telephone and couldn't refer to a picture?