N Queens

The N Queens puzzle challenges the player to place N chess queens on an NxN chessboard so that no two queens threaten each other. Since a queen can attack along its row, column, and both diagonals, no two queens may share the same row, column, or diagonal. The classic version uses an 8x8 board with 8 queens, but the puzzle can be played on any size board from 4x4 upward (there is no solution for 2x2 or 3x3). The number of distinct solutions grows rapidly with board size — the 8-queen problem has 92 solutions (12 unique when considering symmetry).

Rules

1. Place N queens on an NxN chessboard.
2. No two queens may be in the same row.
3. No two queens may be in the same column.
4. No two queens may be on the same diagonal (both directions).
5. All N queens must be placed simultaneously on the board.

Strategies

• Row-by-Row Placement: Place one queen per row, starting from the top. This automatically satisfies the row constraint and reduces the problem to choosing a column for each row.
• Column Tracking: Keep track of which columns are already occupied. Each new queen must go in an unused column.
• Diagonal Tracking: For the two diagonal directions, cells on the same diagonal share a constant value of (row - column) or (row + column). Track these values to quickly identify safe squares.
• Backtracking: If you reach a row where no column is safe, go back to the previous row and try the next available column. This systematic approach guarantees finding a solution.
• Symmetry Exploitation: Solutions can be rotated 90°, 180°, 270° and reflected. Finding one solution gives you up to 8 related solutions for free.
• Start from Corners: Placing a queen in a corner immediately eliminates many squares, which paradoxically can make the remaining placement easier by reducing choices.

The N Queens puzzle originated as the "Eight Queens Puzzle," first proposed in 1848 by the chess player Max Bezzel in the German chess magazine Schachzeitung. The challenge of placing eight queens on a standard chessboard so that none attack each other captured the imagination of mathematicians and chess enthusiasts alike.

The first solutions were published in 1850 by Franz Nauck, who also generalized the problem to N queens on an NxN board. The great mathematician Carl Friedrich Gauss became interested in the problem and corresponded about it with his friend Heinrich Schumacher, though Gauss initially found only 72 of the 92 solutions for the 8-queen case and mistakenly believed that was the complete set.

The puzzle became a foundational problem in computer science. In 1972, Edsger Dijkstra used the 8 Queens problem to illustrate the power of structured programming and the backtracking algorithm. It remains one of the most commonly assigned programming exercises in university computer science courses, used to teach recursion, constraint satisfaction, and algorithm design. It also serves as a benchmark for comparing the efficiency of different search algorithms and constraint propagation techniques.

The N Queens problem has connections to many areas of mathematics, including combinatorics, group theory (through its symmetries), and linear algebra. In 2021, a significant breakthrough was made when Michael Simkin proved an asymptotic formula for the number of solutions, confirming a long-standing conjecture. The problem also has practical applications in parallel memory storage, VLSI circuit testing, and traffic control. Despite its seemingly simple statement, the N Queens problem continues to reveal new mathematical depth.