The Eight Queens Problem
Volume Number: 13
Issue Number: 12
Column Tag: Programming Techniques
Solving The Eight Queens Problem
by F.C. Kuechmann
Using the graphics of a Macintosh to explore the recursion
and backtracking-based solution to this common puzzle
One of the oldest and most familiar intellectual puzzles whose solution is uniquely
suited to the computer is the eight queens problem, in which the goal is to
systematically determine each of the 92 different ways eight queens can be placed on a
chessboard without conflict. Of the 92 solutions, 12 [numbers 1, 2, 5, 6, 7, 8, 9, 10,
11, 14, 17 and 18] are unique; the remaining 80 are variations on the twelve --
mirror images on the vertical, horizontal or diagonal axes, or 90, 180 or 270 degree
rotations.
Since queens can move any number of squares in any direction, each queen must be
placed on its own row, column and diagonals. Niklaus Wirth [1976, 1986] describes
it as a familiar problem and states that Gauss considered it as early as 1850. No
straightforward mathematical formula has ever been devised for its solution. The
trial-and-error method, often combined with such problem solving techniques as
recursion and backtracking, while tedious and error prone for humans, is well-suited
to the computer. (A computer doesn't get bored, make mistakes, or have a cat that
jumps onto the chess board.) Each time the active queen is moved to a new position the
new location is tested for conflict unless that position is off the board. In that case, we
backtrack to the previous column or row, advance that previously secure queen, and
proceed. Thus a backtrack involves a move without testing the new position for
conflict. 981 queen moves (876 position tests plus 105 backtracks) are required for
the first solution alone. 16,704 moves (14,852 tests and 1852 backtracks) are
needed to find all 92 solutions. If we continue testing until all possibilities are
exhausted, we've made 17,684 moves -- 15,720 tests plus 1964 backtracks. Given
those figures, it's easy to see why the solution is best left to computers.
While text-oriented computers can determine the solutions as well as any, a
graphically-oriented computer like the Mac is ideally suited for illustrating the
underlying algorithm.
The widespread use of the personal computer as a teaching tool has contributed to the
appearance of the eight queens problem in several textbooks in the past 20-plus
years, including especially Wirth [1976, 1986] and Budd [1987, 1991, 1996].
Niklaus Wirth's solutions are in Pascal and Modula-2. Timothy Budd has discussed
object-oriented solutions, in languages ranging from SmallTalk to Object Pascal to
Java, in at least three books. Microware furnished a structured BASIC version of
Wirth's Pascal solution with their BASIC09 interpreter, which probably received its
widest distribution packaged for the Radio Shack Color Computer 2 and 3.
A web search on the phrase "eight queens" will uncover several graphic Java
solutions, some interactive, based on a problem posed by Budd [1996]. For some
reason with my PowerPC Mac 6500/225 and Quadra 650, Microsoft's Internet
Explorer browser works better in displaying the interactive Java versions on the web
than does Netscape's Navigator.
WIRTH's Algorithm
The queen conflict tracking mechanism employed by Wirth consists of three Boolean
arrays that track queen status for each row and diagonal. TRUE means no queen is on
that row or diagonal; FALSE means a queen is already there.
Figure 1 shows the mapping of the arrays to the chess board for Pascal. All array
elements are initialized to TRUE. The Row array elements 1-8 correspond to rows
1-8 on the board. A queen in row n sets rows array element n to FALSE.
Column-Row array elements are numbered from -7 to 7 and correspond to the
difference between column and row numbers.
A queen at column 1, row 1 sets array element zero to FALSE. A queen at column 1,
row 8 sets array element -7 to FALSE.
The Column+Row array elements are numbered 2-16 and correspond to the sum of the
column and row. A queen placed in column 1, row 1 sets array element 2 to FALSE. A
queen placed in column 3, row 5 sets array element 8 to FALSE.
Figures 2, 3 and 4 show the changes in array element values as 1, 2 and 3 queens
are placed on the board.
In Figure 2, Row array element 1, Column-Row array element 0, and Column+Row
array element 2 are all set to FALSE.
Figure 2. One conflict queen
Figure 3. Two conflict-free queens.
In Figure 3, Row array element 3, Column-Row array element -1, and Column+Row
Array element 5 are set also set FALSE.
Figure 4. Three conflict-free queens.
In Figure 4, Row Array element 5, Column-Row array element -2, and Column+Row
array element 8 are added to the FALSE list.
It would require hundreds of pages to show the entire move sequence just for the first