N-Queens Count
Hard · rating 1900 · Backtracking
Read an integer n. Print the number of ways to place n non-attacking queens on an n×n board.
Constraints: 1 ≤ n ≤ 12
Editorial
Approach
Place one queen per row and backtrack. A queen at (r, c) attacks a column, a “↓” diagonal (constant r - c) and a “↘” diagonal (constant r + c). Track the used columns and both diagonals in sets; when a full board of n rows is placed, count it.
Why the diagonal keys work
Every cell on the same ↓ diagonal shares r - c, and every cell on the same ↘ diagonal shares r + c, so an O(1) membership check rules out attacks.
def bt(r, cols, d1, d2):
if r == n: count += 1; return
for c in range(n):
if c in cols or r-c in d1 or r+c in d2: continue
bt(r+1, cols|{c}, d1|{r-c}, d2|{r+c})Complexity
Time: exponential in n (far below n! thanks to pruning). Space: O(n) recursion depth.