nqueens

N-Queens, or NQueens, is a classic puzzle in which N queens must be placed on an N×N chessboard so that no two queens attack each other. An attack occurs when two queens share the same row, column, or diagonal. Because a valid solution uses one queen per row and per column, solutions correspond to permutations of column indices with the diagonal constraints acting as additional restrictions.

History and origin: The puzzle is a 19th‑century problem that became popular in mathematical and chess literature. Franz Nauck published the first known list of solutions for N = 8 in 1849, and the eight‑queens puzzle quickly entered broader recreational mathematics and computer science discussions.

Existence, counting, and variants: Solutions exist for all N except N = 2 and N = 3; for N = 1 the solution is trivial. The number of distinct solutions (arrangements) is known for many N; for example, there are 2 solutions for N = 4, 10 for N = 5, 92 for N = 8, and 724 for N = 10. The total count grows rapidly with N, and counts are often reported with and without symmetry reductions (rotations and reflections).

Algorithms and approaches: Solving N-Queens is a standard search problem. The conventional approach is backtracking, building a placement row by row and pruning conflicts as soon as they arise. Efficient implementations use bitwise representations, constraint propagation, or reformulate the problem as an exact cover problem and apply Knuth’s Algorithm X with Dancing Links. The problem is also used as a benchmark in SAT and constraint‑programming tools.

Constructive methods and applications: In addition to exhaustive search, there are constructive patterns that yield valid solutions for many N without exploring the entire search space. N-Queens serves as an educational example of combinatorial search, algorithm design, and problem modeling. See also eight‑queens puzzle and related algorithmic techniques.