The Eight Queens Problem

The problem of the eight queens is a well-known example of the use of trial-and-error methods and of backtracking algorithms. It was investigated by C. F. Gauss in 1850, but he did not completely solve it. This should not surprise anyone. After all, the characteristic property of these problems is that they defy analytic solution. Instead, they require large amounts of exacting labor, patience, and accuracy. Such algorithms have therefore gained relevance almost exclusively through the automatic computer, which possesses these properties to a much higher degree than people, and even geniuses, do.

The eight queens problem is stated as follows (see also [3-4]): Eight queens are to be placed on a chess board in such a way that no queen checks against any other queen.

Using the schema of Eq. (3.29) as a template, we readily obtain the following crude version of a solution:

In order to proceed, it is necessary to make some commitments concerning the data representation. Since we know from the rules of chess that a queen checks all other figures lying in either the same column, row, or diagonals on the board, we infer that each column may contain one and only one queen, and that the choice of a position for the ith queen may be restricted to the ith column. The parameter i therefore becomes the column index, and the selection process for positions then ranges over the eight possible values for a row index j.

There remains the question of representing the eight queens on the board. An obvious choice would again be a square matrix to represent the board,144 but a little inspection reveals that such a representation would lead to fairly cumbersome operations for checking the availability of positions. This is highly undesirable since it is the most frequently executed operation. We should therefore choose a data representation which makes checking as simple as possible. The best recipe is to represent as directly as possible that information which is truly relevant and most often used. In our case this is not the position of the queens, but whether or not a queen has already been placed along each row and diagonals. (We already know that exactly one is placed in each column k for 1 < k <i). This leads to the following choice of variables:

c[k] means no queen sits on the Ath. -diagonal.

The choice for index bounds 61, 62, cl, c2 is dictated by the way that indices of b and c are computed; we note that in a / -diagonal all fields have the same sums of their coordinates i and j, and that in a\, -diagonal the coordinate differences i — j are constant. The appropriate solution is shown in Program 3.4.

and the condition safe is fulfilled if the field <i, 7> lies in a row and in diagonals which are still free (represented by true). Hence, it can be expressed by the logical expression

This completes the development of this algorithm, which is shown in full

Before we abandon the context of the chess board, the eight queens example is to serve as an illustration of an important extension of the trial-anderror algorithm. The extension is—in general terms—to find not only one, but all solutions to a posed problem.

The extension is easily accommodated. We are to recall the fact that the generation of candidates must progress in a systematic manner which guarantees that no candidate is generated more than once. This property of the algorithm corresponds to a search of the candidate tree in a systematic fashion in which every node is visited exactly once. It allows—once a solution is found and duly recorded—merely to proceed to the next candidate delivered by the systematic selection process. The general schema is derived from (3.29) and shown in (3.35)

Note that because of the simplification of the termination condition of the selection process to the single term k = m, the repeat statement is appropriately replaced by a for statement. It comes as a surprise that the search for all possible solutions is realized by a simpler program than the search for a single solution.

The extended algorithm to determine all 92 solutions of the eight queens problem is shown in Program 3.5. Actually, there are only 12 significantly differing solutions; our program does not recognize symmetries. The 12