The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that none of them can capture any other using the standard chess queen's moves. The queens must be placed in such a way that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general nqueens problem of placing n queens on an n×n chessboard, where solutions exist only for n = 1 or n ≥ 4.
Contents
History
The puzzle was originally proposed in 1848 by the chess player Max Bezzel, and over the years, many mathematicians, including Gauss, have worked on this puzzle and its generalized nqueens problem. The first solutions were provided by Franz Nauck in 1850. Nauck also extended the puzzle to nqueens problem (on an n×n board—a chessboard of arbitrary size). In 1874, S. Günther proposed a method of finding solutions by using determinants, and J.W.L. Glaisher refined this approach.
Edsger Dijkstra used this problem in 1972 to illustrate the power of what he called structured programming. He published a highly detailed description of the development of a depthfirst backtracking algorithm.^{2}
Constructing a solution
The problem can be quite computationally expensive as there are 4,426,165,368 (i.e., 64 choose 8) possible arrangements of eight queens on a 8×8 board, but only 92 solutions. It is possible to use shortcuts that reduce computational requirements or rules of thumb that avoids brute force computational techniques. For example, just by applying a simple rule that constrains each queen to a single column (or row), though still considered brute force, it is possible to reduce the number of possibilities to just 16,777,216 (that is, 8^{8}) possible combinations. Generating the permutations that are solutions of the eight rooks puzzle^{[1]} and then checking for diagonal attacks further reduces the possibilities to just 40,320 (that is, 8!). These are computationally manageable for n = 8, but would be intractable for problems of n ≥ 20, as 20! = 2.433 * 10^{18}. Extremely interesting advancements for this and other toy problems is the development and application of heuristics (rules of thumb) that yield solutions to the n queens puzzle at an astounding fraction of the computational requirements.
Full article ▸
