N-Queens

Problem Statement

Place $N$ chess queens on an $N \times N$ chessboard so that no two queens threaten each other. Queens attack along rows, columns, and both diagonals. Return all distinct solutions, each represented as a board configuration.

Example — N=4:

There are exactly 2 solutions:

Solution 1:          Solution 2:
. Q . .              . . Q .
. . . Q              Q . . .
Q . . .              . . . Q
. . Q .              . Q . .

For $N = 8$, there are 92 solutions. The problem generalizes to any $N$, with no solutions for $N = 2$ and $N = 3$.

This is LeetCode 51 — a textbook backtracking problem and one of the most frequently asked in interviews.

Backtracking Framework

Backtracking follows a try, check, undo pattern. The general template:

1. Choose: Make a decision at the current step (place a queen in a column).
2. Constraint: Verify the decision doesn’t violate any rules.
3. Goal: If all decisions are made, record the solution.
4. Backtrack: Undo the decision and try the next option.

function backtrack(state):
    if state is a complete solution:
        record solution
        return
    for each choice in available choices:
        if choice is valid:
            apply choice
            backtrack(updated state)
            undo choice          ← the "backtrack" step

The power of backtracking over brute force: pruning. When a partial assignment violates a constraint, the entire subtree below it is skipped. For N-Queens, this transforms $O(N^N)$ brute force into approximately $O(N!)$ actual work.

Key Insight: Place Row by Row

Since each row must contain exactly one queen, iterate through rows sequentially: row 0, row 1, …, row $N - 1$. In each row, try every column $0$ through $N - 1$.

This design eliminates row conflicts by construction — no two queens ever share a row. Only three types of conflict remain to check:

• Same column
• Same primary diagonal
• Same anti-diagonal

Constraint Checking — Three Threats

Column Conflict

Two queens conflict if they occupy the same column. Track occupied columns in a set.

Diagonal Conflicts — The Indexing Trick

The key insight that separates strong candidates from average ones:

Primary diagonal (top-left to bottom-right): All cells on the same primary diagonal share the same value of row - col.

         col 0   col 1   col 2   col 3
row 0:   0-0=0   0-1=-1  0-2=-2  0-3=-3
row 1:   1-0=1   1-1=0   1-2=-1  1-3=-2
row 2:   2-0=2   2-1=1   2-2=0   2-3=-1
row 3:   3-0=3   3-1=2   3-2=1   3-3=0

Cells (0,0), (1,1), (2,2), (3,3) all have row - col = 0 — the main diagonal.

Anti-diagonal (top-right to bottom-left): All cells on the same anti-diagonal share the same value of row + col.

         col 0   col 1   col 2   col 3
row 0:   0+0=0   0+1=1   0+2=2   0+3=3
row 1:   1+0=1   1+1=2   1+2=3   1+3=4
row 2:   2+0=2   2+1=3   2+2=4   2+3=5
row 3:   3+0=3   3+1=4   3+2=5   3+3=6

Cells (0,3), (1,2), (2,1), (3,0) all have row + col = 3 — one anti-diagonal.

By maintaining three sets — columns, primaryDiagonals (storing row - col), and antiDiagonals (storing row + col) — every constraint check becomes $O(1)$.

Implementation

Naive Constraint Check — O(N) per Check

Scan all previously placed queens and compare against each:

boolean isSafe(int[] queens, int row, int col) {
    for (int prevRow = 0; prevRow < row; prevRow++) {
        int prevCol = queens[prevRow];
        if (prevCol == col) return false;                          // same column
        if (Math.abs(prevRow - row) == Math.abs(prevCol - col))    // same diagonal
            return false;
    }
    return true;
}

This works but performs $O(N)$ comparisons per placement. Over the entire search, the constraint checking overhead adds up.

Optimized Constraint Check — O(1) per Check

Replace the linear scan with three HashSet lookups:

import java.util.*;

public class NQueens {

    private final Set<Integer> columns = new HashSet<>();
    private final Set<Integer> primaryDiags = new HashSet<>();   // row - col
    private final Set<Integer> antiDiags = new HashSet<>();      // row + col

    private void placeQueen(int row, int col) {
        columns.add(col);
        primaryDiags.add(row - col);
        antiDiags.add(row + col);
    }

    private void removeQueen(int row, int col) {
        columns.remove(col);
        primaryDiags.remove(row - col);
        antiDiags.remove(row + col);
    }

    private boolean isUnderAttack(int row, int col) {
        return columns.contains(col)
            || primaryDiags.contains(row - col)
            || antiDiags.contains(row + col);
    }
}

Each placement and removal operates in $O(1)$. Each safety check is three hash set lookups — $O(1)$ amortized.

Building the Board

Track queen positions as int[] queens where queens[row] = col. Convert to the List<List<String>> output format when a complete solution is found:

List<String> buildBoard(int[] queens, int n) {
    var board = new ArrayList<String>();
    for (int row = 0; row < n; row++) {
        char[] rowChars = new char[n];
        Arrays.fill(rowChars, '.');
        rowChars[queens[row]] = 'Q';
        board.add(new String(rowChars));
    }
    return board;
}

Complete Solution

Full Java 25 solution with clean recursive backtracking:

import java.util.*;

public class NQueens {

    public List<List<String>> solveNQueens(int n) {
        var results = new ArrayList<List<String>>();
        var queens = new int[n];
        Arrays.fill(queens, -1);
        var columns = new HashSet<Integer>();
        var primaryDiags = new HashSet<Integer>();
        var antiDiags = new HashSet<Integer>();

        backtrack(0, n, queens, columns, primaryDiags, antiDiags, results);
        return results;
    }

    private void backtrack(int row, int n, int[] queens,
                           Set<Integer> columns,
                           Set<Integer> primaryDiags,
                           Set<Integer> antiDiags,
                           List<List<String>> results) {
        if (row == n) {
            results.add(buildBoard(queens, n));
            return;
        }

        for (int col = 0; col < n; col++) {
            int diag = row - col;
            int antiDiag = row + col;

            if (columns.contains(col) || primaryDiags.contains(diag) || antiDiags.contains(antiDiag)) {
                continue;   // pruned — this placement conflicts
            }

            // Place queen
            queens[row] = col;
            columns.add(col);
            primaryDiags.add(diag);
            antiDiags.add(antiDiag);

            // Recurse to next row
            backtrack(row + 1, n, queens, columns, primaryDiags, antiDiags, results);

            // Backtrack — remove queen
            queens[row] = -1;
            columns.remove(col);
            primaryDiags.remove(diag);
            antiDiags.remove(antiDiag);
        }
    }

    private List<String> buildBoard(int[] queens, int n) {
        var board = new ArrayList<String>();
        for (int row = 0; row < n; row++) {
            char[] rowChars = new char[n];
            Arrays.fill(rowChars, '.');
            rowChars[queens[row]] = 'Q';
            board.add(new String(rowChars));
        }
        return board;
    }
}

Search Tree Visualization

For $N = 4$, the backtracking search tree with pruning:

Row 0: Try col 0
  Row 1: Try col 0 — PRUNED (column)
  Row 1: Try col 1 — PRUNED (diagonal)
  Row 1: Try col 2
    Row 2: Try col 0 — PRUNED (anti-diagonal)
    Row 2: Try col 1 — PRUNED (column)
    Row 2: Try col 2 — PRUNED (column)
    Row 2: Try col 3 — PRUNED (diagonal)
  Row 1: Try col 3
    Row 2: Try col 0 — PRUNED (anti-diagonal)
    Row 2: Try col 1
      Row 3: Try col 0 — PRUNED (diagonal)
      Row 3: Try col 1 — PRUNED (column)
      Row 3: Try col 2 — PRUNED (anti-diagonal)
      Row 3: Try col 3 — PRUNED (column)
    Row 2: ...

Row 0: Try col 1
  Row 1: Try col 0 — PRUNED (diagonal)
  Row 1: Try col 1 — PRUNED (column)
  Row 1: Try col 2 — PRUNED (diagonal)
  Row 1: Try col 3
    Row 2: Try col 0
      Row 3: Try col 0 — PRUNED (column)
      Row 3: Try col 1 — PRUNED (anti-diagonal)
      Row 3: Try col 2 ✓ SOLUTION FOUND!
        → [.Q.., ...Q, Q..., ..Q.]
    Row 2: ...

Row 0: Try col 2
  Row 1: Try col 0
    Row 2: Try col 3
      Row 3: Try col 1 ✓ SOLUTION FOUND!
        → [..Q., Q..., ...Q, .Q..]
    Row 2: ...
  ...

Out of $4^4 = 256$ brute-force placements, backtracking explores only ~24 nodes before finding both solutions. The pruning ratio grows dramatically with $N$ — for $N = 8$, brute force checks $8^8 \approx 16.7M$ placements while backtracking explores ~15,720.

Complexity Analysis

Time Complexity: $O(N!)$

At row 0, there are $N$ column choices. At row 1, at most $N - 1$ columns are free (one blocked by column constraint). At row 2, at most $N - 2$. Diagonal constraints prune even further, but the upper bound becomes:

$$T(N) \leq N \cdot (N - 1) \cdot (N - 2) \cdots 1 = N!$$

The actual number of nodes explored is closer to $N \cdot (N-2) \cdot (N-4) \cdots$ due to diagonal pruning — tighter than $N!$ but hard to express in closed form.

Space Complexity: $O(N^2)$

• $O(N)$ for the queens array and the three tracking sets.
• $O(N)$ for recursion depth (one frame per row).
• $O(N^2)$ for storing each solution board (but producing output is inherent to the problem).

Number of solutions by $N$:

N	Solutions
1	1
2	0
3	0
4	2
5	10
6	4
7	40
8	92
9	352
10	724
12	14,200

The count grows roughly exponentially but with no known closed-form formula.

Variations

N-Queens II: Count Solutions Only

When only the count is needed, skip board construction entirely. The backtracking structure remains identical — increment a counter instead of building a board:

public int totalNQueens(int n) {
    return countSolutions(0, n, new HashSet<>(), new HashSet<>(), new HashSet<>());
}

private int countSolutions(int row, int n,
                           Set<Integer> columns,
                           Set<Integer> primaryDiags,
                           Set<Integer> antiDiags) {
    if (row == n) return 1;

    int count = 0;
    for (int col = 0; col < n; col++) {
        int diag = row - col;
        int antiDiag = row + col;
        if (columns.contains(col) || primaryDiags.contains(diag) || antiDiags.contains(antiDiag)) {
            continue;
        }
        columns.add(col);
        primaryDiags.add(diag);
        antiDiags.add(antiDiag);
        count += countSolutions(row + 1, n, columns, primaryDiags, antiDiags);
        columns.remove(col);
        primaryDiags.remove(diag);
        antiDiags.remove(antiDiag);
    }
    return count;
}

Bit Manipulation Optimization

Replace HashSet with integer bitmasks for the fastest constraint checking. Each bit represents a column or diagonal index. The bitwise OR of all three masks with the candidate position gives an $O(1)$ conflict test with zero overhead from hashing:

public int totalNQueensBits(int n) {
    return countWithBits(0, n, 0, 0, 0);
}

private int countWithBits(int row, int n, int columns, int primaryDiags, int antiDiags) {
    if (row == n) return 1;

    int availablePositions = ((1 << n) - 1) & ~(columns | primaryDiags | antiDiags);
    int count = 0;

    while (availablePositions != 0) {
        int position = availablePositions & (-availablePositions);   // lowest set bit
        availablePositions ^= position;                              // remove it

        count += countWithBits(
            row + 1, n,
            columns | position,
            (primaryDiags | position) << 1,
            (antiDiags | position) >> 1
        );
    }
    return count;
}

The bit trick availablePositions & (-availablePositions) isolates the lowest set bit — the next column to try. The shift operations propagate diagonal constraints down to the next row. This avoids all memory allocation and runs significantly faster for large $N$.

Connecting Backtracking to Other Problems

N-Queens is the prototype for an entire class of constraint satisfaction problems. The same backtracking template applies to:

Problem	Choose	Constraint	Goal
N-Queens	Column for current row	No column/diagonal conflict	All rows filled
Sudoku	Digit for current cell	No row/col/box duplicate	All cells filled
Permutations	Next element to place	Not already used	All elements placed
Combinations	Include or skip element	Size limit, ordering	Target size reached
Graph coloring	Color for current node	No adjacent same color	All nodes colored

The structure is identical — only the constraint function and choice space change. Mastering N-Queens transfers directly to all these problems.

Edge Cases

N	Behavior
1	Trivial: [["Q"]] — one queen on a 1×1 board.
2	No solutions — any queen placement attacks all remaining cells.
3	No solutions — verified by exhaustive search.
0	Edge case: return [[]] or empty depending on interpretation.
Large N (> 15)	Solutions exist for all $N \geq 4$, but enumeration becomes impractical. Use counting-only variant or randomized algorithms.

Interviewer Tips

The diagonal indexing trick — row - col for primary diagonals, row + col for anti-diagonals — is the KEY insight. Explain it with a small grid drawn on the whiteboard. Interviewers look for whether you discovered this yourself or memorized the solution.

Recommended interview flow:

1. Start with the brute-force analysis: $N^N$ placements, explain why row-by-row reduces to $N!$.
2. Explain the three constraints and the diagonal trick with a visual.
3. Write the backtracking solution with HashSet.
4. Mention the bit manipulation optimization as a follow-up.

Common follow-ups:

• N-Queens II: How would you modify your code to return only the count? (Remove board construction.)
• Bit manipulation: Can you replace the sets with bitmasks for speed? (Show the bitwise approach.)
• Very large N: How would you find one solution for $N = 1000$? (Constraint propagation with arc consistency, or Las Vegas randomized algorithms that place queens with random restarts.)
• Symmetry reduction: The 92 solutions for $N = 8$ reduce to 12 unique solutions under rotation and reflection. How would you eliminate symmetric duplicates?