0

N-Queens

Hard

Place one queen per row. Track attacked columns and both diagonals in sets so every safety check is constant time.

backtrackingpruningconstraint sets
TimeExponential, heavily pruned
SpaceO(n)
InputBoard size from 4 to 8

Empty 6 by 6 board. Queens attack along rows, columns and both diagonals.

placements0backtracks0solutions0
1 / 474
place(row):
if row == n: record solution; return
for col in 0..n-1:
if col or diagonals attacked: skip
mark; place(row+1); unmark // undo is mandatory
Why it matters

Row plus column identifies one diagonal, row minus column the other. That is the whole trick.

Practise this
N-QueensHSudoku SolverHM-Coloring ProblemMRat in a Maze ProblemM
Keyboard
space play← → stepr restartctrl K search

More in Recursion & Backtracking

Subsets (Take or Skip)
O(n * 2^n)
Permutations (Swap and Recurse)
O(n! * n)
Sudoku Solver
Exponential in theory, instant in practice
Next visualiser
Subsets (Take or Skip)