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)
Nearby terms:
eigenvector « eight-bit clean « eight queens problem
«
eight queens puzzle » eighty-column mind »
eighty-twenty rule » EISA
|
