N-Queens — DSA-30

N-Queens hard

Description

The N-Queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other — meaning no two share a row, column, or diagonal.

Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration where 'Q' indicates a queen and '.' indicates an empty cell.

Examples

> Case 1:
    n = 4
    Output: [
        [".Q..",
         "...Q",
         "Q...",
         "..Q."],
        [
         "..Q.",
         "Q...",
         "...Q",
         ".Q.."]
    ]
 
> Case 2:
    n = 1
    Output: [["Q"]]

Constraints

1 <= n <= 9

State design

The defining example of constraint placement with incremental state.

Partial solution? queens[] — the column index of the queen in each row processed so far. Plus three sets: cols, diag1 (the / diagonals indexed by r + c), diag2 (the \ diagonals indexed by r - c).
Complete? When we’ve placed queens in all n rows.
Choices? Every column c in row r.
Legality? c not in cols AND (r + c) not in diag1 AND (r - c) not in diag2 — O(1) lookups thanks to the maintained sets.
Undo? Remove the column/diagonal from each set after recursing.

We process row by row (one queen per row), so we never have to worry about row conflicts.

Code

Why r + c for one diagonal and r - c for the other?

Cells on the same /-diagonal (top-right to bottom-left) all share the same value of r + c. Cells on the same \-diagonal (top-left to bottom-right) all share r - c. So (r + c) and (r - c) are perfect unique IDs for the two diagonal families.

For the C++/Java arrays we use (r - c + n) to shift the range into [0, 2n) so it can index a boolean array.

A bitmask micro-optimization

For competitive programming, the cols / d1 / d2 sets can be encoded as three integers and updated with bit shifts. Placing a queen at column c of row r:

cols |= (1 << c)
d1 = (d1 | (1 << c)) << 1 (shift left so it represents row r+1’s diagonal)
d2 = (d2 | (1 << c)) >> 1

The legality check becomes !(cols | d1 | d2) and the available-columns mask is ~(cols | d1 | d2) & ((1 << n) - 1). This solves N = 14 in milliseconds and N = 20 in a few seconds — out of scope for interviews but conceptually beautiful.

Analysis

Time: O(N!) in the worst case, but the diagonal pruning slashes that to roughly O(N^N) divided by exponential factors. In practice: N = 8 runs in microseconds; N = 13 is the last one solvable in well under a second by the standard backtracking version.
Space: O(N) recursion + O(N) state sets.

Same skin

N-Queens II — return only the COUNT (not the boards).
Sudoku Solver (next problem) — same idea, 3-way constraints (row / col / box).
Graph Coloring — assign one of k colors per vertex; no two adjacent vertices same color.
Knight’s Tour — visit every cell of a chessboard exactly once with knight moves.

Restore IP Addresses Sudoku Solver