The eight queens puzzle is the problem of placing eight chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
The queen is the most powerful piece in the game of chess, able to move any number of squares vertically, horizontally, or diagonally. Each player starts the game with one queen, placed in the middle of the first rank next to the king. With the chessboard oriented correctly, the white queen starts...
s on an 8×8 chessboard so 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 for all natural numbers n with the exception of 2 and 3.
History
The puzzle was originally proposed in 1848 by the chess player Max Bezzel
Max Bezzel
Max Friedrich William Bezzel was a German chess composer who created the eight queens puzzle in 1848.-External links:*...
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Johann Carl Friedrich Gauss was a German mathematician and scientist who contributed significantly to many fields, including number theory, statistics, analysis, differential geometry, geodesy, geophysics, electrostatics, astronomy and optics.Sometimes referred to as the Princeps mathematicorum...
, 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 determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
Edsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...
used this problem in 1972 to illustrate the power of what he called structured programming
Structured programming
Structured programming is a programming paradigm aimed on improving the clarity, quality, and development time of a computer program by making extensive use of subroutines, block structures and for and while loops - in contrast to using simple tests and jumps such as the goto statement which could...
. He published a highly detailed description of the development of a depth-first
Depth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
.2
Constructing a solution
The problem can be quite computationally expensive as there are 4,426,165,368 (i.e., 64 choose
Combination
In mathematics a combination is a way of selecting several things out of a larger group, where order does not matter. In smaller cases it is possible to count the number of combinations...
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
Brute-force search
In computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's...
. 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 permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s that are solutions of the eight rooks puzzle and then checking for diagonal attacks further reduces the possibilities to just 40,320 (that is, 8!
Factorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
code uses this technique to calculate the 92 solutions:
from itertools import permutations
n = 8
cols = range(n)
for vec in permutations(cols):
if (n
len(set(vec[i]+i for i in cols))
len(set(vec[i]-i for i in cols))):
print vec
These brute-force algorithms are computationally manageable for n = 8, but would be intractable for problems of n ≥ 20, as 20! = 2.433 * 1018. Advancements for this and other toy problem
Toy problem
In scientific disciplines, a toy problem is a problem that is not of immediate scientific interest, yet is used as an expository device to illustrate a trait that may be shared by other, more complicated, instances of the problem, or as a way to explain a particular, more general, problem solving...
s are the development and application of heuristics (rules of thumb) that yield solutions to the n queens puzzle at a small fraction of the computational requirements.
This heuristic solves N queens for any N ≥ 4. It forms the list of numbers for vertical positions (rows) of queens with horizontal position (column) simply increasing. N is 8 for eight queens puzzle.
If the remainder from dividing N by 6 is not 2 or 3 then the list is simply all even numbers followed by all odd numbers ≤ N
Otherwise, write separate lists of even and odd numbers (i.e. 2,4,6,8 - 1,3,5,7)
If the remainder is 2, swap 1 and 3 in odd list and move 5 to the end (i.e. 3,1,7,5)
If the remainder is 3, move 2 to the end of even list and 1,3 to the end of odd list (i.e. 4,6,8,2 - 5,7,9,1,3)
Append odd list to the even list and place queens in the rows given by these numbers, from left to right (i.e. a2, b4, c6, d8, e3, f1, g7, h5)
For N = 8 this results in the solution shown above. A few more examples follow.
The eight queens puzzle has 92 distinct solutions. If solutions that differ only by symmetry operation
Symmetry
Symmetry generally conveys two primary meanings. The first is an imprecise sense of harmonious or aesthetically pleasing proportionality and balance; such that it reflects beauty or perfection...
s (rotations and reflections) of the board are counted as one
Up to
In mathematics, the phrase "up to x" means "disregarding a possible difference in x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...
, the puzzle has 12 unique (or fundamental) solutions.
A fundamental solution usually has 8 variants (including its original form) obtained by rotating 90, 180, or 270 degrees and then reflecting each of the four rotational variants in a mirror in a fixed position. However, should a solution be equivalent to its own 90 degree rotation (as happens to one solution with 5 queens on a 5x5 board) that fundamental solution will have only 2 variants. Should a solution be equivalent to its own 180 degree rotation it will have 4 variants. Of the 12 fundamental solutions to the problem with 8 Queens on an 8x8 board, exactly 1 is equal to its own 180 degree rotation, and none are equal to their 90 degree rotation. Thus the number of distinct solutions is 11*8 + 1*4 = 92.
The unique solutions are presented below:
Explicit solutions
Explicit solutions exist for placing n queens on an n × n board, requiring no combinatorial search whatsoever .
The explicit solutions exhibit stair-stepped patterns, as in the following examples for n = 8, 9 and 10:
Counting solutions
The following table gives the number of solutions for placing n queens on an n × n board, both unique and distinct , for n=1–14, 24–26.
n:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
..
24
25
26
unique:
1
0
0
1
2
1
6
12
46
92
341
1,787
9,233
45,752
..
28,439,272,956,934
275,986,683,743,434
2,789,712,466,510,289
distinct:
1
0
0
2
10
4
40
92
352
724
2,680
14,200
73,712
365,596
..
227,514,171,973,736
2,207,893,435,808,352
22,317,699,616,364,044
Note that the six queens puzzle has fewer solutions than the five queens puzzle.
There is currently no known formula for the exact number of solutions.
The knight is a piece in the game of chess, representing a knight . It is normally represented by a horse's head and neck. Each player starts with two knights, which begin on the row closest to the player, one square from the corner...
A bishop is a piece in the board game of chess. Each player begins the game with two bishops. One starts between the king's knight and the king, the other between the queen's knight and the queen...
In chess, the king is the most important piece. The object of the game is to trap the opponent's king so that its escape is not possible . If a player's king is threatened with capture, it is said to be in check, and the player must remove the threat of capture on the next move. If this cannot be...
A fairy chess piece or unorthodox chess piece is a piece analogous to a chess piece. It is not used in conventional chess, but is used in certain chess variants and some chess problems...
s have also been substituted for queens. In the case of knights, an easy solution is to place one on each square of a given color, since they move only to the opposite color.
In mathematics, a Costas array can be regarded geometrically as a set of n points lying on the squares of a n×n checkerboard, such that each row or column contains only one point, and that all of the n/2 displacement vectors between each pair of dots are distinct...
In mathematics, a Costas array can be regarded geometrically as a set of n points lying on the squares of a nxn chessboard, such that each row or column contains only one point, and that all of the n(n − 1)/2 displacement vectors between each pair of dots are distinct. Thus, an order-n Costas array is a solution to an n-rooks puzzle.
George Pólya was a Hungarian mathematician. He was a professor of mathematics from 1914 to 1940 at ETH Zürich and from 1940 to 1953 at Stanford University. He made fundamental contributions to combinatorics, number theory, numerical analysis and probability theory...
In geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with the circle...
("donut-shaped") board and showed that there is a solution on an n×n board if and only if n is not divisible by 2 or 3. In 2009 Pearson and Pearson algorithmically populated three-dimensional boards (n×n×n) with n2 queens, and proposed that multiples of these can yield solutions for a four-dimensional version of the puzzle.
Domination
Given an n×n board, the domination number is the minimum number of queens (or other pieces) needed to attack or occupy every square. For n=8 the queen's domination number is 5.
Place nine queens and one pawn on an 8×8 board in such a way that queens don't attack each other. Further generalization of the problem (complete solution is currently unknown): given an n×n chess board and m > n queens, find the minimum number of pawns, so that the m queens and the pawns can be set up on the board in such a way that no two queens attack each other.
In recreational mathematics, a magic square of order n is an arrangement of n2 numbers, usually distinct integers, in a square, such that the n numbers in all rows, all columns, and both diagonals sum to the same constant. A normal magic square contains the integers from 1 to n2...
s
In 1992, Demirörs, Rafraf, and Tanik published a method for converting some magic squares into n queens solutions, and vice versa.
In combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column...
s
In an n×n matrix, place each digit 1 through n in n locations in the matrix so that no two instances of the same digit are in the same row or column.
Consider a matrix with one primary column for each of the n ranks of the board, one primary column for each of the n files, and one secondary column for each of the 4n-6 nontrivial diagonals of the board. The matrix has n2 rows: one for each possible queen placement, and each row has a 1 in the columns corresponding to that square's rank, file, and diagonals and a 0 in all the other columns. Then the n queens problem is equivalent to choosing a subset of the rows of this matrix such that every primary column has a 1 in precisely one of the chosen rows and every secondary column has a 1 in at most one of the chosen rows; this is an example of a generalized exact cover problem, of which sudoku
Sudoku
is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid contains all of the digits from 1 to 9...
is another example.
The eight queens puzzle as an exercise in algorithm design
Finding all solutions to the eight queens puzzle is a good example of a simple but nontrivial problem. For this reason, it is often used as an example problem for various programming techniques, including nontraditional approaches such as constraint programming
Constraint programming
Constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties...
Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s. Most often, it is used as an example of a problem which can be solved with a recursive
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
, by phrasing the n queens problem inductively in terms of adding a single queen to any solution to the problem of placing n−1 queens on an n-by-n chessboard. The induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
bottoms out with the solution to the 'problem' of placing 0 queens on an 0-by-0 chessboard, which is the empty chessboard.
In computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's...
algorithm, which considers all 648 = 248 = 281,474,976,710,656 possible blind placements of eight queens, and then filters these to remove all placements that place two queens either on the same square (leaving only 64!/56! = 178,462,987,637,760 possible placements) or in mutually attacking positions. This very poor algorithm will, among other things, produce the same results over and over again in all the different permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s of the assignments of the eight queens, as well as repeating the same computations over and over again for the different sub-sets of each solution. A better brute-force algorithm places a single queen on each row, leading to only 88 = 224 = 16,777,216 blind placements.
It is possible to do much better than this.
One algorithm solves the eight rooks
Rook (chess)
A rook is a piece in the strategy board game of chess. Formerly the piece was called the castle, tower, marquess, rector, and comes...
puzzle by generating the permutations of the numbers 1 through 8 (of which there are 8! = 40,320), and uses the elements of each permutation as indices to place a queen on each row.
Then it rejects those boards with diagonal attacking positions.
The backtracking
Backtracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
program, a slight improvement on the permutation method, constructs the search tree
Search tree
In computer science, a search tree is a binary tree data structure in whose nodes data values are stored from some ordered set, in such a way that in-order traversal of the tree visits the nodes in ascending order of the stored values...
by considering one row of the board at a time, eliminating most nonsolution board positions at a very early stage in their construction.
Because it rejects rook and diagonal attacks even on incomplete boards, it examines only 15,720 possible queen placements.
A further improvement which examines only 5,508 possible queen
placements is to combine the permutation based method with the early
pruning method: the permutations are generated depth-first, and
the search space is pruned if the partial permutation produces a
diagonal attack. Constraint programming
Constraint programming
Constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties...
can also be very effective on this problem.
An alternative to exhaustive search is an 'iterative repair' algorithm, which typically starts with all queens on the board, for example with one queen per column. It then counts the number of conflicts (attacks), and uses a heuristic to determine how to improve the placement of the queens. The 'minimum-conflicts' heuristic
Heuristic
Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...
— moving the piece with the largest number of conflicts to the square in the same column where the number of conflicts is smallest — is particularly effective: it finds a solution to the 1,000,000 queen problem in less than 50 steps on average. This assumes that the initial configuration is 'reasonably good' — if a million queens all start in the same row, it will obviously take at least 999,999 steps to fix it. A 'reasonably good' starting point can for instance be found by putting each queen in its own row and column so that it conflicts with the smallest number of queens already on the board.
Note that 'iterative repair', unlike the 'backtracking' search outlined above, does not guarantee a solution: like all hillclimbing (i.e., greedy
Greedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
) procedures, it may get stuck on a local optimum (in which case the algorithm may be restarted with a different initial configuration). On the other hand, it can solve problem sizes that are several orders of magnitude beyond the scope of a depth-first search.
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
to solve the problem. A queen is placed in a column that is known not to cause conflict. If a column is not found the program returns to the last good state and then tries a different column.
Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
Niklaus Emil Wirth is a Swiss computer scientist, best known for designing several programming languages, including Pascal, and for pioneering several classic topics in software engineering. In 1984 he won the Turing Award for developing a sequence of innovative computer languages.-Biography:Wirth...
. It finds one solution to the eight queens problem.
program eightqueen1(output);
var i : integer; q : boolean;
a : array[ 1 .. 8] of boolean;
b : array[ 2 .. 16] of boolean;
c : array[ -7 .. 7] of boolean;
x : array[ 1 .. 8] of integer;
procedure try( i : integer; var q : boolean);
var j : integer;
begin j := 0;
repeat j := j + 1; q := false;
if a[ j] and b[ i + j] and c[ i - j] then
begin x[ i] := j;
a[ j] := false; b[ i + j] := false; c[ i - j] := false;
if i < 8 then
begin try( i + 1, q);
if not q then
begin a[ j] := true; b[ i + j] := true; c[ i - j] := true;
end
end else q := true
end
until q or (j = 8);
end;
begin
for i := 1 to 8 do a[ i] := true;
for i := 2 to 16 do b[ i] := true;
for i := -7 to 7 do c[ i] := true;
try( 1, q);
if q then
for i := 1 to 8 do write( x[ i]:4);
writeln
end.
A mathematical game is a multiplayer game whose rules, strategies, and outcomes can be studied and explained by mathematics. Examples of such games are Tic-tac-toe and Dots and Boxes, to name a couple. On the surface, a game need not seem mathematical or complicated to still be a mathematical game...
Mathematical puzzles make up an integral part of recreational mathematics. They have specific rules as do multiplayer games, but they do not usually involve competition between two or more players. Instead, to solve such a puzzle, the solver must find a solution that satisfies the given conditions....
In mathematics, in the area of discrete geometry, the no-three-in-line-problem, introduced by Henry Dudeney in 1917, asks for the maximum number of points that can be placed in the n × n grid so that no three points are collinear...
In combinatorial mathematics, a rook polynomial is a generating polynomial of the number of ways to place non-attacking rooks on a board that looks like a checkerboard; that is, no two rooks may be in the same row or column...
Visual Prolog, also formerly known as PDC Prolog and Turbo Prolog, is a strongly typed object-oriented extension of Prolog. As Turbo Prolog it was marketed by Borland, but it is now developed and marketed by the Danish firm Prolog Development Center that originally developed it...
Rosetta Code is a wiki-based programming chrestomathy website with solutions to various programming problems in many different programming languages. It was created in 2007 by Mike Mol. Rosetta Code includes 450 programming tasks, and covers 351 programming languages...
ANS-Forth solution Non-recursive with backtracking (demonstrates how Forth functions can take variable numbers of parameters on the stack). Also, an implementation of the heuristic algorithm described earlier in this Wikipedia article (demonstrates linked lists).
