51. N-Queens

Array
Backtracking
Recursion

TIME

O(n!)

SPACE

O(n) excluding the output

Intuition

Two queens attack along a row, a column, or a diagonal. Placing exactly one queen per row satisfies the row constraint by construction, so the search only has to choose a column for each row, turning the board into a sequence of n decisions rather than n^2 cell choices.

The remaining three conflicts have cheap constant-time tests if the right quantities are tracked:

Column: the column index itself.
**Main diagonal (\):** every cell on it shares the same row - col.
Anti-diagonal (/): every cell on it shares the same row + col.

Keeping a set for each means "is this square attacked?" is three lookups, and undoing a placement is three removals, the essence of backtracking.

Approach

Recurse on the current row, starting at row 0.
For each column c in that row:
- Skip if c is in cols, or row - c is in diags, or row + c is in antis.
- Otherwise record the placement, add the three keys, and recurse on row + 1.
- On return, remove the keys and undo the placement (backtrack).
When the row index reaches n, every row holds a queen, render the placement into strings and append it to the results.

Complexity

Time: O(n!) in the worst case, the branching shrinks by at least one column per row, and pruning cuts far more in practice
Space: O(n) for the recursion and the three sets, plus O(number of solutions * n) for the output

Edge Cases

n == 1 → a single solution, [["Q"]]
n == 2 and n == 3 → no solutions, so an empty list is returned
Diagonal keys row - col can be negative; a set (or an offset array) handles that
Each solution is generated once because rows are filled in a fixed order, so no de-duplication is needed
n <= 9 keeps the search small (the largest case, n = 9, has 352 solutions)

Code

from typing import List


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        """
        51. N-Queens
        Time: O(n!)
        Space: O(n) excluding the output
        """
        result = []
        placement = [-1] * n          # placement[row] = chosen column
        cols = set()
        diags = set()                 # row - col, constant along "\"
        antis = set()                 # row + col, constant along "/"

        def backtrack(row: int) -> None:
            if row == n:
                result.append([
                    "." * c + "Q" + "." * (n - c - 1) for c in placement
                ])
                return
            for c in range(n):
                if c in cols or (row - c) in diags or (row + c) in antis:
                    continue
                placement[row] = c
                cols.add(c)
                diags.add(row - c)
                antis.add(row + c)

                backtrack(row + 1)

                cols.remove(c)
                diags.remove(row - c)
                antis.remove(row + c)
                placement[row] = -1

        backtrack(0)
        return result

import java.util.ArrayList;
import java.util.List;

/**
 * 51. N-Queens
 * Time: O(n!)
 * Space: O(n) excluding the output
 */
class Solution {
    private int n;
    private int[] placement;      // placement[row] = chosen column
    private boolean[] cols;
    private boolean[] diags;      // indexed by row - col + n, constant along "\"
    private boolean[] antis;      // indexed by row + col, constant along "/"
    private List<List<String>> result;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        placement = new int[n];
        cols = new boolean[n];
        diags = new boolean[2 * n];
        antis = new boolean[2 * n];
        result = new ArrayList<>();
        backtrack(0);
        return result;
    }

    private void backtrack(int row) {
        if (row == n) {
            List<String> board = new ArrayList<>(n);
            for (int c : placement) {
                char[] line = new char[n];
                java.util.Arrays.fill(line, '.');
                line[c] = 'Q';
                board.add(new String(line));
            }
            result.add(board);
            return;
        }
        for (int c = 0; c < n; c++) {
            int d = row - c + n, a = row + c;
            if (cols[c] || diags[d] || antis[a]) {
                continue;
            }
            placement[row] = c;
            cols[c] = diags[d] = antis[a] = true;

            backtrack(row + 1);

            cols[c] = diags[d] = antis[a] = false;
        }
    }
}