Nqueensongelma

Nqueensongelma, known in English as the N-Queens problem, is a classic puzzle in combinatorics and computer science. The goal is to place N queens on an N×N chessboard so that no two queens attack each other, meaning no two queens share the same row, column, or diagonal.

Mathematically, a solution can be described by a permutation p of the numbers 1 through N, where queen i is placed at row i and column p(i). The constraints are that p(i) ≠ p(j) for i ≠ j (inherent in a permutation) and |i − j| ≠ |p(i) − p(j)| for all i ≠ j (no diagonal conflicts).

Existence and counts: Solutions exist for all N except N = 2 and N = 3. The number of distinct solutions (not counting symmetry) for N = 1..12 is: 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200. If board symmetries are considered equivalent, the counts are smaller.

Solutions and methods: The problem is typically solved by backtracking, constraint programming, or reduction to an exact cover problem solved by Knuth’s Algorithm X with dancing links. There are explicit constructive methods that place N queens for all N ≥ 4. The N-Queens problem is widely used as a benchmark for algorithm design and for illustrating search techniques, heuristics, and optimization.

Variants: Variants include counting all solutions, finding a single solution, or using toroidal or partially filled boards. The problem remains a foundational example of combinatorial search in both mathematics and computer science.