eight queens puzzle

algorithm A puzzle in which one has to place eight queens on

a chessboard such that no queen is attacking any other,

i.e. no two queens occupy the same row, column or diagonal.

One may have to produce all possible such configurations or

just one.

It is a common students assignment to devise a program to

solve the eight queens puzzle. The brute force algorithm

tries all 64*63*62*61*60*59*58*57 = 178,462,987,637,760

possible layouts of eight pieces on a chessboard to see which

ones meet the criterion. More intelligent algorithms use the

fact that there are only ten positions for the first queen

that are not reflections of each other, and that the first

queen leaves at most 42 safe squares, giving only

10*42*41*40*39*38*37*36 = 1,359,707,731,200 layouts to try,

and so on.

The puzzle may be varied with different number of pieces and

different size boards.

[Best algorithm?]

(1999-07-28)