N-Queens

Problem. Place $n$ queens on an $n\times n$ board so that no two attack each other (no shared row, column or diagonal). Count the solutions, or find one.

Backtracking with bitmasks — the standard solution

Place one queen per row; track occupied columns and both diagonal families as bitmasks.

long long count = 0;
void solve(int row, int cols, int d1, int d2, int n) {
    if (row == n) { count++; return; }
    int avail = ~(cols | d1 | d2) & ((1 << n) - 1);
    while (avail) {
        int bit = avail & -avail;
        avail ^= bit;
        solve(row + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1, n);
    }
}
// call: solve(0, 0, 0, 0, n)

The shifts propagate the diagonals automatically: a queen at column $c$ in row $r$ blocks column $c+1$ of the "$\searrow$" family in row $r+1$, which is exactly (d1 | bit) << 1.

avail & -avail isolates the lowest available column, so the loop visits each candidate once. $n=15$ runs in well under a second; $n=17$ takes a few seconds.

Solution counts

$n$	Solutions	$n$	Solutions
1	1	8	92
2	0	9	352
3	0	10	724
4	2	12	14 200
5	10	15	2 279 184
6	4	20	$3.9\cdot 10^{10}$
7	40	27	$2.3\cdot 10^{17}$ (the largest computed)

No closed form is known, and counting is believed hard. $n=27$ was computed in 2016 with a large distributed effort.

Constructing one solution in $O(n)$

Counting is hard; finding a single solution is easy. Explicit formulas exist for every $n\ge 4$:

• $n$ even, $n\not\equiv 2(\mathrm{mod}6)$: place queens at $(i,2i)$ for $i\le n/2$ and $(i,2i-n-1)$ for the rest.
• Other cases have similar formulas with small adjustments.

So “output any valid placement” is $O(n)$ and needs no search at all — worth knowing, because contest versions usually ask for a solution, not the count.

Symmetry breaking

The board has 8 symmetries (the dihedral group $D_4$). Restricting the first queen to the first half of the first row roughly halves the search, and correcting for the fixed points recovers the exact count.

More aggressive: classify solutions by their symmetry class (asymmetric, 180°-symmetric, 90°-symmetric) and count each with the appropriate multiplier — a Burnside argument.

As exact cover

N-Queens is an exact cover problem with:

• primary columns (must be covered exactly once): each rank, each file;
• secondary columns (at most once): each of the $2(2n-1)$ diagonals.

Dancing Links with optional columns solves it directly, and this is the standard demonstration of secondary columns.

Variants

Variant	Note
Count solutions	no closed form; $n\le 17$ by search
Find any solution	$O(n)$ construction
Solutions up to symmetry	”fundamental” solutions; 12 for $n=8$
Queens on a torus	solvable iff $\gcd (n,6)=1$
$n$ superqueens (queen + knight moves)	much more constrained
Minimum queens to dominate the board	a different (domination) problem
Maximum non-attacking rooks	trivially $n$
Maximum non-attacking knights	$\lceil n^2/2\rceil$ — one colour class
Maximum non-attacking bishops	$2n-2$
Peaceable queens (two armies)	an open problem

Why it is worth knowing

It is the canonical demonstration of three ideas:

1. Bitmask state — three integers encode all the constraints, and the transitions are shifts.
2. Backtracking with $O(1)$ constraint checks — the pruning is free.
3. Counting is harder than constructing — a recurring asymmetry (see also permanent vs determinant, and matchings).

See also: Backtracking · Dancing Links · Bit Operations