Place n queens on an n×n board so that no two attack each other — no shared row, column, or diagonal.

The catch: even with one queen per row enforced up front, the search still explodes combinatorially. Backtracking tames it by rejecting partial placements the moment they become invalid, instead of building full candidates and checking later.

How It Works

1. Try each column of the current row.
2. Check the column and both diagonals against queens already placed.
3. Place a queen if safe, then recurse to the next row.
4. Prune the branch immediately when the position is attacked.
5. Backtrack — if a row has no safe column, remove the previous queen and advance it to its next column.

Because exactly one queen sits in each row, you only track the column of each placed queen — the board state is a single array, and the safety test reduces to comparing columns and diagonal differences.

Key Insight

The solver explores the search tree depth-first and prunes as soon as a partial placement becomes invalid. That’s the entire point of backtracking: constraints are checked during construction.

• Without pruning — C(n², n) candidate placements.
• With pruning — roughly n! / e arrangements: still exponential, but drastically smaller.

The moment row k has no safe column, the solver stops descending and unwinds.

Worked Example

The visualizer solves the 6×6 board (N = 6). Watch the queens appear one row at a time, left to right. Early rows place quickly; then a row finds no safe column, the solver undoes the previous queen, advances it, and resumes. The final frame shows all 6 queens placed with no two sharing a row, column, or diagonal:

. Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .

Each placed queen eliminates its entire column and both diagonals from the rows below — the safety check that makes the solution legal.

Edge Cases & Pitfalls

• N < 4 — there is no solution for N = 2 or N = 3: the solver must report failure, not loop forever.
• All diagonals — a queen attacks along r + c (one diagonal family) and r − c (the other). Track both sets.
• Symmetry — rotations/reflections of one solution are all valid; a solver finds just one by default.
• Premature cutoff — pruning must not reject a square that a deeper queen could still make safe. Safety only checks already-placed queens.

Comparison: N-Queens Search Strategies

Applications

• Constraint satisfaction — timetabling and scheduling use the same search
• Graph coloring — place “colors” without adjacent conflicts
• Puzzle solving — Sudoku, crosswords, and fill-in puzzles

Practice Trajectory

1. Trace the visualizer: note each row’s first safe column and where the first backtrack happens.
2. Derive why N = 2 and N = 3 have no solution before running the solver.
3. Implement the safety check using only the column array — no 2D board needed.
4. Add symmetry pruning and count how many distinct solutions N = 6 has (4 total, 1 up to symmetry; N = 8 has 92, 12 up to symmetry).
5. Explain why the recursion depth is exactly n, not n².