Eight queens puzzle

One solution.

The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is 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 and n ≥ 4.

[edit] History

The puzzle was originally proposed in 1848 by the chess player Max Bezzel, and over the years, many mathematicians, including Gauss and Georg Cantor, 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). In 1874, S. Gunther 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.²

This puzzle appeared in the popular early 1990s computer game The 7th Guest.

[edit] Constructing a solution

The problem can be quite computationally expensive as there are 4,426,165,368 (64×63×...×58×57/8!, where the "!" stands for Factorial) possible arrangements, 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 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. This heuristic solves n queens for any n n ≥ 4 or n = 1:

1. Divide n by 12. Remember the remainder (n is 8 for the eight queens puzzle).
2. Write a list of the even numbers from 2 to n in order.
3. If the remainder is 3 or 9, move 2 to the end of the list.
4. 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, …).
5. If the remainder is 2, switch the places of 1 and 3, then move 5 to the end of the list.
6. If the remainder is 3 or 9, move 1 and 3 to the end of the list.
7. 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.

[edit] Solutions to the eight queens puzzle

The eight queens puzzle has 92 distinct solutions. If solutions that differ only by symmetry operations (rotations and reflections) of the board are counted as one, the puzzle has 12 unique (or fundamental) solutions, which are presented below:

Unique solution 1	Unique solution 2	Unique solution 3
Unique solution 4	Unique solution 5	Unique solution 6