N-Queens

DSA · Advanced

Definition

Place N queens on an N×N board so none attack each other.

The standard backtracking showcase.

Diagram

Flowchart

Example: Count solutions

def solve(n):
    cols, d1, d2 = set(), set(), set()
    def go(r):
        if r == n: return 1
        cnt = 0
        for c in range(n):
            if c in cols or r - c in d1 or r + c in d2: continue
            cols.add(c); d1.add(r - c); d2.add(r + c)
            cnt += go(r + 1)
            cols.remove(c); d1.remove(r - c); d2.remove(r + c)
        return cnt
    return go(0)
print(solve(4), solve(8))

Output: 2 92

Complexity

About O(n!)

Key points

r−c and r+c identify diagonals
Sets give O(1) checks

Interview questions

Why one queen per row?

Two queens in a row attack each other, so each row holds exactly one.