The
eight queens puzzle is the problem of putting eight
chessChess is a board game played between two players. The current form of the game emerged in Southern Europe during the second half of the 15th century after evolving from a similar, much older game of Indian origin...
queenThe queen is the most powerful piece in the game of chess. Each player starts the game with one queen, placed in the middle of their first rank next to their king. The white queen starts on a white square, and the black queen on a black square, thus the mnemonic "queen gets her color" or "queen on...
s on an 8×8 chessboard such that none of them are able to capture any other using the standard chess queen's moves. The queens must be placed in such a way that no two queens would be able to 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 puzzle of placing n
queens on an n
×n
chessboard, where solutions exist only for n
= 1 or n ≥ 4.
History
The puzzle was originally proposed in 1848 by the chess player
Max BezzelMax Friedrich William Bezzel was a German chess composer who created the eight queens puzzle in 1848.-External links:*...
, and over the years, many
mathematicianA mathematician is a person whose primary area of study and/or research is the field of mathematics. Mathematicians are concerned with particular problems related to logic, space, transformations, numbers and more general ideas which encompass these concepts...
s, including
GaussJohann 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...
and
Georg CantorGeorg Ferdinand Ludwig Phillip Cantor was a German mathematician, born in Russia. He is best known as the creator of set theory, which has become a fundamental theory in mathematics...
, 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. Gunther proposed a method of finding solutions by using
determinantIn algebra, the determinant is a special number associated to any square matrix, that is to say, a rectangular array of numbers where the number of rows and columns are equal. The fundamental geometric meaning of a determinant is a scale factor for measure when the matrix is regarded as a linear...
s, and J.W.L. Glaisher refined this approach.
Edsger DijkstraEdsger 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 programmingStructured programming can be seen as a subset or subdiscipline of procedural programming, one of the major programming paradigms. It is most famous for removing or reducing reliance on the GOTO statement....
. He published a highly detailed description of the development of a
depth-firstDepth-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 algorithmBacktracking 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...
.
2
This puzzle appeared in the popular early 1990s computer game
The 7th GuestThe 7th Guest, first published in 1992 by Trilobyte and later released by Virgin Games in 1993, is a FMV-based puzzle video game, not unlike The Fool's Errand and predating Myst. It was one of the first computer video games to be released only on CD-ROM. The 7th Guest is a horror story told from...
.
Constructing a solution
The problem can be quite computationally expensive as there are 4,426,165,368 (or 64
!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...
/(56
!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...
8
!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...
)) possible arrangements of eight queens on the 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 (8^8) possible combinations, which is computationally manageable for n=8, but would be intractable for problems of n=1,000,000. Extremely interesting advancements for this and other
toy problemIn mathematics and information science, 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,...
s 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. This heuristic solves n
queens for any n n
≥ 4 or n
= 1:
- Divide
n
by 12. Remember the remainder (n
is 8 for the eight queens puzzle).
Write a list of the even numbers from 2 to n
in order.
If the remainder is 3 or 9, move 2 to the end of the list.
Append the odd numbers from 1 to n in order, but, if the remainder is 8, switch pairs (i.e. 3, 1, 7, 5, 11, 9, …).
If the remainder is 2, switch the places of 1 and 3, then move 5 to the end of the list.
If the remainder is 3 or 9, move 1 and 3 to the end of the list.
Place the first-column queen in the row with the first number in the list, place the second-column queen in the row with the second number in the list, etc.
For n = 8 this results in the solution shown above. A few more examples follow.
- 14 queens (remainder 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
- 15 queens (remainder 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
- 20 queens (remainder 8): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17.
Solutions to the eight queens puzzle
The eight queens puzzle has 92 distinct
solutions. If solutions that differ only by symmetry operationSymmetry 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 oneIn mathematics, the phrase "up to xxxx" indicates that members of an equivalence class are to be regarded as a single entity for some purpose. "xxxx" describes a property or process which transforms an element into one from the same equivalence class, i.e. one to which it is considered equivalent...
, the puzzle has 12 unique
(or fundamental) solutions, which are presented below:
Counting solutions
The following table gives the number of solutions for placing n
queens on an n
× n
board, both unique and distinct .
| 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.
Related problems
Using pieces other than queens
- For example, on an 8×8 board one can place 32 knight
The knight is a piece in the game of chess, representing a knight . It is normally represented by a horse's head, leading some to refer to it informally as a "horse"....
s, or 14 bishopA 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...
s, 16 kingIn chess, the King is the most important piece. The object of the game is to trap the opponent's king so that he would not be able to avoid capture . If a player's king is threatened with capture, he is said to be in check, and the player must move so as to remove the threat of capture...
s or 8 rookA rook is a piece in the strategy board game of chess. In the past the piece was called the castle, tower, marquess, rector, and comes , and non-players still often call it a "castle". Using the rook in a specialized double-movement with the king is still refered to as castling...
s, so that no two pieces attack each other. Fairy chess pieceA fairy chess piece or unorthodox chess piece is a chess piece not used in conventional chess, but 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.
Nonstandard boards
- Pólya
George Pólya was a Hungarian mathematician.-Life and works:He was born as Pólya György in Budapest, Hungary to originally Jewish parents Anna Deutsch and Jakab Pólya who converted to Roman Catholicism in 1886...
studied the n queens problem on a toroidalIn geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with and not touching the circle. Examples of tori include the surfaces of doughnuts and inner tubes. The solid contained by the surface is known as a toroid...
("donut-shaped") board. 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, find the domination number, which is the minimum number of queens (or other pieces) needed to attack or occupy every square. For the 8×8 board, the queen's domination number is 5.
Nine queens problem
- 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.
Queens and knights problem
- Place m queens and m knights on an n×n board such that no piece attacks another.
Magic squareIn recreational mathematics, a magic square of order n is an arrangement of n² 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 n²...
s
- In 1992, Demirörs, Rafraf, and Tanik published a method for converting some magic squares into n queens solutions, and vice versa.
Latin squareA Latin square is an n × n table filled with n different symbols in such a way that each symbol occurs exactly once in each row and exactly once in each column. Here is an example:
...
s
- In an n×n matrix, place each digit 1 through n in n locations in the matrix such that no two instances of the same digit are in the same row or column.
Exact coverIn mathematics, given a collection of subsets of a set X, an exact cover is a subcollection of such that each element in X is contained in exactly one subset in .One says that each element in X is covered by exactly one subset in ....
- 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
In mathematics, given a collection of subsets of a set X, an exact cover is a subcollection of such that each element in X is contained in exactly one subset in .One says that each element in X is covered by exactly one subset in ....
problem, of which sudokuis a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid...
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 programmingConstraint programming is a programming paradigm where 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 programmingLogic 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...
or
genetic algorithmA genetic algorithm is a search technique used in computing to find exact or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics...
s. Most often, it is used as an example of a problem which can be solved with a
recursiveRecursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition. The term is also used more generally to describe a process of repeating objects in a self-similar way...
algorithmIn mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....
, 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
inductionMathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite...
bottoms out with the solution to the 'problem' of placing 0 queens on an n-by-n chessboard, which is the empty chessboard.
This technique is much more efficient than the naïve
brute-force searchIn 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 64
8 = 2
48 = 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
permutationIn several fields of mathematics the term permutation is used with different but closely related meanings. They all relate to the notion of mapping the elements of a set to other elements of the same set, i.e., exchanging elements of a set.- Definitions :The general concept of permutation can be...
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 8
8 = 2
24 = 16,777,216 blind placements.
It is possible to do much better than this.
One algorithm generates 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, guaranteeing no
rookA rook is a piece in the strategy board game of chess. In the past the piece was called the castle, tower, marquess, rector, and comes , and non-players still often call it a "castle". Using the rook in a specialized double-movement with the king is still refered to as castling...
attacks.
Then it rejects those boards with diagonal attacking positions.
The
backtrackingBacktracking 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...
depth-first searchDepth-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 treeIn computer science, a search tree is a tree data structure in whose nodes data values can be stored from some ordered set, which is such that in an in-order traversal of the tree the nodes are visited in ascending order of the stored values. Each subtree of a search tree is by itself again a...
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 programmingConstraint programming is a programming paradigm where 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'
heuristicHeuristic is an adjective for experience-based techniques that help in problem solving, learning and discovery. A heuristic method is particularly used to rapidly come to a solution that is hoped to be close to the best possible answer, or 'optimal solution'...
— 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 solves 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 such 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 non-hillclimbing (i.e., greedy) 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.
An animated version of the recursive solution
This animation uses
backtrackingBacktracking 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...
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.
Algorithms that solve the eight queens puzzle implemented in different programming languages are found in the
eight queens puzzle solutionsThis article shows algorithmic solutions to the eight queens puzzle implemented in various computer programming languages. For specific outcomes of these algorithms, see the main eight queens puzzle article.-Board representations:...
article.
See also
- Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
- Mathematical game
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 puzzle
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...
- No-three-in-line problem
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...
- Rook polynomial
In combinatorics, rook polynomials are a specific type of generating polynomials. Their name comes from their original use: to determine how many ways one can place a collection of non-attacking rooks on a chessboard...
- Distributed Computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
- BOINC
External links
Links to solutions
N Queens solutions on Sloane's
On-Line Encyclopedia of Integer SequencesThe On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is a freely-available online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs, and hosted on his website....