A Placement Problem on the Chessboard
The Eight-Queens Puzzle asks that eight queens be placed on an 8×8 chessboard so that none can attack another using the usual queen moves. Because of this, no two queens may share a row, a column, or a diagonal. The puzzle is a special case of the more general n-Queens Puzzle, which places n queens on an n×n board for any n ≥ 4.
Origins and Early Study
According to the source, the Eight-Queens Puzzle, together with its general form, was first posed in 1848 by chess player Max Bezzel. Over the following years it was examined by many mathematicians, including Gauss and Georg Cantor. The first solution appeared in 1850, produced by Franz Nauck, who also extended the puzzle to n queens on an n×n board. Later, in 1972, Edsger Dijkstra used the Eight-Queens problem in an algorithm he created to demonstrate the power of a method he called structural programming.
Why the Solution Requires Heavy Computation
The source notes that the total number of possible arrangements equals 283,274,583,552, expressed as 64×63×…×58×57 divided by 8!. Despite this enormous figure, only 92 solutions exist, so solving the puzzle demands substantial computation. To reduce wasted calculations, some shortcuts can be applied. For example, enforcing the constraint that only one queen may appear in each row or column lowers the number of possibilities to 16,777,216, written as 8⁸.
An Algorithmic Approach to the n-Queens Puzzle
The source describes a sequence of steps that can be followed in order to find a solution to the n-Queens Puzzle. First, divide n by 12 and keep the remainder (for the Eight-Queens Puzzle, n equals 8). Then write out all even numbers from 2 up to n. If the remainder is 3 or 9, place the number 2 at the end of the list. Next, add the odd numbers from 1 to n to the list; if the remainder is 8, swap positions among the even numbers themselves, as in the example 3, 1, 7, 5, 11, 9, …. If the remainder is 2, swap 1 and 3 and 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. Finally, place a queen in the row indicated by each number of the list for the corresponding column. For instance, if the first number in the list is 2, a queen must be placed in the second row of the first column.
Illustrative Lists
The source provides several example lists. For 14 queens, with a remainder of 2, the list reads 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5. For 15 queens, with a remainder of 3, it reads 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3. For 20 queens, with a remainder of 8, the list is 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17.
Counting Distinct Solutions
The source states that the Eight-Queens Puzzle has 92 distinct solutions, though most of them arise from one another through symmetry operations such as rotation and reflection. If these symmetry-generated duplicates are merged into a single solution, the puzzle actually has 12 essentially distinct solutions.
Notable Observation on Solution Counts
The source includes a table of solution counts for various values of n and highlights a striking detail: the number of solutions on a 6×6 board is smaller than the number on a 5×5 board.
This explanation is adapted from Wikipedia and is available under CC BY-SA 4.0.
1 comment