Eight Queens

The Eight Queens Problem
by John Sigle

Can you place eight queens on a chess board so that no two are attacking each
other, that is, so that no two are on the same row, column, or diagonal? Yes,
it can be done! This program is an animated demonstration of an algorithm to
solve this problem. It is adapted from a program in the book ^1Algorithms + Data
^1Structures = Programs^0 by Niklaus Wirth, Prentice-Hall, 1976.

This program makes good use of recursion to search for a solution. It places
queens on the board column by column. In order to place eight queens safely on
the board, it places a queen safely in the first column and then tries to place
the seven remaining queens safely on the board. The latter problem (placing
seven queens safely) is the same problem as the original (placing eight queens)
only smaller in size. This leads to a recursive solution.

The program also illustrates backtracking, a method commonly used in
applications requiring searching, such as many areas of artificial intelligence.
When a "dead end" is reached (it is impossible to place any more of the
remaining queens safely) the most recently placed queen is removed from its
placement and advanced to a new position, if possible. If it cannot be advanced
then it is removed entirely and the next most recently placed queen is advanced,
and so on.

The choice of data structures in this program is also interesting. It does
not use a 2-dimensional array to represent the board as you might expect. The
most frequent task to be done by the program is testing to see if a position is
safe, that is, whether or not any queens lie on the same row or diagonal as that
position. The order of attempted queen placement (column by column) insures that
no queen lies on the same column. The data structures are chosen in order to
make the testing task convenient and efficient. "InRow" is a boolean array
whose i-th element indicates whether a queen has been placed in row i.
Similarly, "InDiag1" is a boolean array whose i-th element indicates whether a
queen has been placed in the i-th / diagonal (a / diagonal slants upward to the
right.) For the numbering scheme shown below, all the positions on a given /
diagonal have the same sum for their column and row numbers. This sum can be
used as an index to uniquely identify a / diagonal. These indices range from 2
thru 16. "InDiag2" records occupancy for the \ diagonals. The column number
minus the row number is constant for all positions on a \ diagonal, and is used
as an index, which ranges from -7 thru +7.

^C^I 1 * * * * * * * * ^N
^C^I 2 * * * * * * * * ^N
^C^I 3 * * * * * * * * ^N
^C^I 4 * * * * * * * * ^N
^C^I 5 * * * * * * * * ^N
^C^I 6 * * * * * * * * ^N
^C^I 7 * * * * * * * * ^N
^C^I 8 * * * * * * * * ^N
^C^I 1 2 3 4 5 6 7 8 ^N

This demo shows the PASCAL program as it executes as well as the data values
being manipulated. In addition it illustrates the program's actions on a chess
board. The demo can be run at varying speeds. It vividly shows the nature of
this searching method and relates it directly to the PASCAL program performing
the task.

You can control the speed by pressing a digit 0-9 (not the numeric keypad) at
any time. Nine is the highest speed while 1 is the lowest. A speed of 0 lets
you single-step through the program by pressing the spacebar twice to execute
each line of the program. Also, by pressing the + key you can switch between
two display modes: Full and Overview. In Full mode every line executed is
displayed. In Overview mode only selected lines, actually comment lines, are
displayed. In Overview mode the demo proceeds more quickly, yet shows the
highlights of the process. You can scroll the program display forward or
backward at any time by means of the up or down arrows. At the conclusion of
the demo the total number of positions tested and queen placements performed is
reported.