N-Queens

Hard#51row by row

Place n chess queens on an n × n board so that no two share a row, a column or a diagonal. Return every such board, drawn with Q for a queen and a dot for an empty cell. Our example: n = 5 has 10 boards.

51 N-QueensWalkthrough · 1×

Example: n = 5. Watch [0, 4, 1]: every column of row 3 is attacked, so the branch dies there and row 2 has nothing else to try.

0123401234results—
free cellqueen above, in the listqueen just placedattacked cell of this rowfull board, saved

Put 5 queens on a 5 × 5 board so that no two attack each other, in every possible way

01/82
restart · back · play · step
Speed
1function solveNQueens(n):
2 results = []
3 place([])
4 return boards drawn from results
5
6function place(queens): // queens[r]: column in row r
7 if len(queens) == n:
8 add copy of queens to results
9 return
10 for c in free columns of row len(queens):
11 place(queens + [c]) // a new list: no undo
state
queens
–
c
–
results
–
click a step to go back

← → step · space play/pause

Why it works

  1. Each row holds exactly one queen, so a call only chooses a column for the next row, and two queens can never share a row.
  2. A queen goes only where no queen above attacks it, so every full board is valid, and a branch dies as soon as a row has no free column instead of after all n queens are placed.
  3. The call gets a new list, queens + [c], so when it returns the caller still has its own list: going back up undoes the queen by itself.

Complexity

Time O(n!) at most: row 0 has n columns to try, row 1 at most n − 1, and so on, and each check looks at up to n queens above; cut branches make it much less in practice. Memory O(n²) besides the answer: up to n calls deep, each with its list of up to n queens.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.