BacktrackingRecursion & Backtracking

N-Queens

Place n queens on an n×n board so none attack each other, by filling one row at a time and pruning columns and diagonals already under attack.

Learn N-Queens →
Solutions (0)
empty
1/25Place 5 queens on a 5×5 board so none share a row, column or diagonal. One queen per row, tried column by column.
QueenAttacked by a queenRow being tried / queen removedSolution
PseudocodeLearn N-Queens →
1solve(row):
2  if row == n: record(board); return
3  for col in 0 .. n-1:
4    if attacked(row, col): continue
5    place(row, col)
6    solve(row + 1)
7    remove(row, col)        // backtrack
Variables
n5
Complexity
worst O(n!)
space O(n)
Speed