Eight queens puzzle

related topics
{math, number, function}
{game, team, player}
{@card@, make, design}
{war, force, army}

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 n-queens 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 n-queens problem. The first solutions were provided by Franz Nauck in 1850. Nauck also extended the puzzle to n-queens 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 depth-first 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, 88) 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 * 1018. 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 ▸

related documents
Knight's tour
Well-order
Diophantine set
Goodstein's theorem
Carmichael number
Kolmogorov space
Cartesian product
Laurent series
Group representation
Local ring
Lebesgue measure
Convex set
Controllability
Axiom of regularity
Conjunctive normal form
Kruskal's algorithm
Euler's totient function
Generalized Riemann hypothesis
Monotonic function
Algebraic topology
Symmetric group
Diffeomorphism
Isomorphism theorem
Tree (data structure)
Automated theorem proving
Mersenne twister
Differential topology
Golomb coding
Analytic geometry
Search algorithm