Problem Statement

N-Queens

A queen in chess attacks every square in her row, her column, and both diagonals. The job here is to put n queens on an n by n board so that none of them attack each other, and to return every possible way to do it. Each answer is drawn as a grid of strings, where 'Q' is a queen and '.' is an empty square. Our main tool is backtracking. Backtracking means we make one choice at a time, go as far as we can, and the moment a choice breaks the rules we undo it and try the next option. Picture exploring a maze: you walk down a path, hit a dead end, walk back to the last fork, and try a different turn. We will place queens one row at a time, and for each row we test each column to see if it is safe.

hardBacktrackingBacktrackingTime: O(n!) · Space: O(n^2)

Signals to notice

place n queens on n×n boardno two attack each otherconstraint satisfaction

Brute force first

Try all n^n placements — exponential. Most are invalid. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

Backtracking row by row: place one queen per row, check column and diagonal conflicts. Use sets for conflict checking. Prune invalid branches early. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `n=4`

row0: col0 safe -> place (0,0); cols={0} diags={0} anti={0}; recurse row1
row1: col0/col1 blocked; col2 safe -> place (1,2); recurse row2
row2: cols 0,2 & diag/anti block every col -> dead end; backtrack to row1, then row0
row0 retry: col1 safe -> place (0,1); cols={1} diags={-1} anti={1}; recurse row1
row1: col3 safe -> place (1,3); cols={1,3}; recurse row2
row2: col0 safe -> place (2,0); cols={0,1,3}; recurse row3
row3: col2 safe -> place (3,2); row==4 -> record solution [".Q..","...Q","Q...","..Q."]
search continues, finds 2nd solution; return [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

What must stay true

One queen per row (since queens attack entire rows). For each row, try each column — check three constraints: column not used, positive diagonal not used, negative diagonal not used. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

backtrack(row):
  if row == n: record board; return
  for col in 0..n-1:
    if col in cols or (row-col) in diags or (row+col) in antiDiags: continue
    place queen; add col,(row-col),(row+col) to sets
    backtrack(row+1)
    remove queen and undo set additions

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not tracking diagonals efficiently — use (row-col) for one diagonal direction and (row+col) for the other. Sets of these values give conflict detection. The fix is usually to return to the meaning of each move, not just the steps themselves.

Backtracking Pattern