N-Queens II

Hard#52row by row

Place n chess queens on an n × n board so that no two share a row, a column or a diagonal, and return how many ways there are. Only the number is needed, not the boards. Our example: n = 5 has 10 ways.

52 N-Queens IIWalkthrough · 1×

Example: n = 5. Watch row 1 right after the queen at (0, 0): (1, 1) has r - c = 0, and 0 is already in d1, so it is on the same diagonal.

0123401234
free cellqueen abovequeen just placedtaken: column or diagonal in a setfull board: one more way

Count the ways to put 5 queens on a 5 × 5 board so that no two attack each other

01/82
restart · back · play · step
Speed
1function totalNQueens(n):
2 count = 0
3 place(0, {}, {}, {})
4 return count
5
6function place(r, cols, d1, d2): // d1: r-c, d2: r+c
7 if r == n:
8 count = count + 1
9 return
10 for c with c ∉ cols, r-c ∉ d1, r+c ∉ d2:
11 place(r + 1, cols + c, d1 + (r-c), d2 + (r+c))
state
r
–
c
–
cols
–
d1
–
d2
–
count
–
click a step to go back

← → step · space play/pause

Why it works

  1. Along a ↘ diagonal r and c grow together, so r - c stays the same; along a ↙ diagonal r + c does. A queen takes its column, its r - c and its r + c, so one look into three sets tells whether a cell is attacked.
  2. Each call fills one row with a column no queen above attacks, so a call at r = n has a full valid board and adds exactly one way, and a row with no free column ends its branch at once.
  3. Each call gets new sets with its queen added, so the caller’s sets stay as they were: going back up removes the queen without any undo.

Complexity

Time O(n!) at most: row 0 has n columns to try, row 1 at most n − 1, and so on; each check is O(1) with the sets, though copying them costs O(n) per call. Memory O(n²): up to n calls deep, each with sets of up to n numbers.

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.