160. N-Queens

Why this mechanism works

Placing exactly one queen in each successive row handles row conflicts automatically. A column set handles vertical conflicts. Diagonals are identified by row-column and row+column, so two more sets replace repeated scans of the board. Each recursive frame reserves these three identifiers and releases them after exploring its row choice.

State and boundaries

columns holds chosen column indices in row order. used_cols, down and up describe all attacks from those placed queens.

Protocol

1. At row n construct and save board strings.
2. Try each column.
3. Skip any occupied column or diagonal.
4. Reserve the three identifiers and append the column.
5. Recurse to the next row.
6. Undo every reservation.

Visualization

row 0: .Q..   column 1, diagonals -1 and 1
row 1: ...Q   column 3, diagonals -2 and 4
row 2: Q...
row 3: ..Q.   one complete nonattacking board

Python implementation

def n_queens(n):
    output, columns = [], []
    used_cols, down, up = set(), set(), set()
    def visit(row):
        if row == n:
            output.append(['.' * c + 'Q' + '.' * (n - c - 1) for c in columns])
            return
        for col in range(n):
            if col in used_cols or row - col in down or row + col in up:
                continue
            columns.append(col)
            used_cols.add(col)
            down.add(row - col)
            up.add(row + col)
            visit(row + 1)
            up.remove(row + col)
            down.remove(row - col)
            used_cols.remove(col)
            columns.pop()
    visit(0)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 n_queens: output, columns = [], []
n=4; columns=[]; output=[]

L3 n_queens: used_cols, down, up = set(), set(), set()
n=4; columns=[]; output=[]; down=set(); up=set(); used_cols=set()

L5 visit: if row == n:
row=0; columns=[]; down=set(); n=4; output=[]; up=set(); used_cols=set()

L8 visit: for col in range(n):
row=0; columns=[]; down=set(); n=4; output=[]; up=set(); used_cols=set(); col=0

L11 visit: columns.append(col)
row=0; columns=[0]; down=set(); n=4; output=[]; up=set(); used_cols=set(); col=0

L12 visit: used_cols.add(col)
row=0; columns=[0]; down=set(); n=4; output=[]; up=set(); used_cols={0}; col=0

L13 visit: down.add(row - col)
row=0; columns=[0]; down={0}; n=4; output=[]; up=set(); used_cols={0}; col=0

L14 visit: up.add(row + col)
row=0; columns=[0]; down={0}; n=4; output=[]; up={0}; used_cols={0}; col=0

... 214 intermediate state changes omitted ...

L17 visit: down.remove(row - col)
row=0; columns=[3]; down=set(); n=4; output=[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]; up=set(); used_cols={3}; col=3

L18 visit: used_cols.remove(col)
row=0; columns=[3]; down=set(); n=4; output=[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]; up=set(); used_cols=set(); col=3

L19 visit: columns.pop()
row=0; columns=[]; down=set(); n=4; output=[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]; up=set(); used_cols=set(); col=3

L20 n_queens: visit(0)
n=4; columns=[]; output=[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]; down=set(); up=set(); used_cols=set()

L2 n_queens: output, columns = [], []
n=2; columns=[]; output=[]

L3 n_queens: used_cols, down, up = set(), set(), set()
n=2; columns=[]; output=[]; down=set(); up=set(); used_cols=set()

L5 visit: if row == n:
row=0; columns=[]; down=set(); n=2; output=[]; up=set(); used_cols=set()

L8 visit: for col in range(n):
row=0; columns=[]; down=set(); n=2; output=[]; up=set(); used_cols=set(); col=0

L11 visit: columns.append(col)
row=0; columns=[0]; down=set(); n=2; output=[]; up=set(); used_cols=set(); col=0

L12 visit: used_cols.add(col)
row=0; columns=[0]; down=set(); n=2; output=[]; up=set(); used_cols={0}; col=0

L13 visit: down.add(row - col)
row=0; columns=[0]; down={0}; n=2; output=[]; up=set(); used_cols={0}; col=0

L14 visit: up.add(row + col)
row=0; columns=[0]; down={0}; n=2; output=[]; up={0}; used_cols={0}; col=0

... 15 intermediate state changes omitted ...

L16 visit: up.remove(row + col)
row=0; columns=[1]; down={-1}; n=2; output=[]; up=set(); used_cols={1}; col=1

L17 visit: down.remove(row - col)
row=0; columns=[1]; down=set(); n=2; output=[]; up=set(); used_cols={1}; col=1

L18 visit: used_cols.remove(col)
row=0; columns=[1]; down=set(); n=2; output=[]; up=set(); used_cols=set(); col=1

L19 visit: columns.pop()
row=0; columns=[]; down=set(); n=2; output=[]; up=set(); used_cols=set(); col=1

Why the solution is correct

The guards prevent every possible attack from an earlier queen, while row progression prevents same-row attacks. Every valid board has a unique sequence of row columns, whose choices remain unblocked and are therefore explored. Cleanup preserves sibling state, and row increases to n.

Time and space

O(n*n! + S*n^2) coarse time bound, including board materialization for S solutions; O(n) auxiliary search state and O(S*n^2) output characters.

Common mistakes

The two diagonal families use different expressions. Removing only the column on return leaves stale diagonal conflicts and silently loses solutions.

Reasoning card

Transfer exercise

Count solutions without constructing boards, then represent attack sets with bit masks and explain the shifted diagonal masks.