N-Queens

Problem Description

The n-queens puzzle asks you to place n queens on an n x n chessboard so that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' indicate a queen and an empty space, respectively.

Examples

Constraints

• 1 ≤ n ≤ 9

Three Constraints, Three Sets

A queen attacks along its row, column, and both diagonals. Place one queen per row (that resolves the row constraint). For each row, pick a column where:

• No other queen occupies that column
• No other queen sits on the same diagonal (top-left to bottom-right)
• No other queen sits on the same anti-diagonal (top-right to bottom-left)

The insight for diagonals: all cells on the same diagonal share the same value of row - col. All cells on the same anti-diagonal share the same value of row + col. Store those values in sets and a column check is an O(1) lookup.

Solution: Backtracking with Diagonal Sets

import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        Set<Integer> cols = new HashSet<>(), diag = new HashSet<>(), antiDiag = new HashSet<>();
        int[] queens = new int[n]; // queens[row] = col
        Arrays.fill(queens, -1);
        backtrack(n, 0, queens, cols, diag, antiDiag, result);
        return result;
    }

    private void backtrack(int n, int row, int[] queens,
                            Set<Integer> cols, Set<Integer> diag, Set<Integer> antiDiag,
                            List<List<String>> result) {
        if (row == n) {
            result.add(buildBoard(queens, n));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (cols.contains(col) || diag.contains(row - col) || antiDiag.contains(row + col)) {
                continue; // this column is under attack
            }

            queens[row] = col;
            cols.add(col);
            diag.add(row - col);
            antiDiag.add(row + col);

            backtrack(n, row + 1, queens, cols, diag, antiDiag, result);

            queens[row] = -1;
            cols.remove(col);
            diag.remove(row - col);
            antiDiag.remove(row + col);
        }
    }

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

class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        result = []
        cols, diag, anti_diag = set(), set(), set()
        queens = [-1] * n

        def backtrack(row: int):
            if row == n:
                board = []
                for r in range(n):
                    line = '.' * queens[r] + 'Q' + '.' * (n - queens[r] - 1)
                    board.append(line)
                result.append(board)
                return

            for col in range(n):
                if col in cols or (row - col) in diag or (row + col) in anti_diag:
                    continue  # this column is under attack

                queens[row] = col
                cols.add(col)
                diag.add(row - col)
                anti_diag.add(row + col)

                backtrack(row + 1)

                queens[row] = -1
                cols.discard(col)
                diag.discard(row - col)
                anti_diag.discard(row + col)

        backtrack(0)
        return result

#include <vector>
#include <string>
#include <unordered_set>

class Solution {
public:
    std::vector<std::vector<std::string>> solveNQueens(int n) {
        std::vector<std::vector<std::string>> result;
        std::unordered_set<int> cols, diag, antiDiag;
        std::vector<int> queens(n, -1);
        backtrack(n, 0, queens, cols, diag, antiDiag, result);
        return result;
    }

private:
    void backtrack(int n, int row, std::vector<int>& queens,
                   std::unordered_set<int>& cols, std::unordered_set<int>& diag,
                   std::unordered_set<int>& antiDiag,
                   std::vector<std::vector<std::string>>& result) {
        if (row == n) {
            std::vector<std::string> board;
            for (int r = 0; r < n; r++) {
                std::string line(n, '.');
                line[queens[r]] = 'Q';
                board.push_back(line);
            }
            result.push_back(board);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (cols.count(col) || diag.count(row - col) || antiDiag.count(row + col)) {
                continue;
            }

            queens[row] = col;
            cols.insert(col); diag.insert(row - col); antiDiag.insert(row + col);

            backtrack(n, row + 1, queens, cols, diag, antiDiag, result);

            queens[row] = -1;
            cols.erase(col); diag.erase(row - col); antiDiag.erase(row + col);
        }
    }
};

Complexity Analysis:

• Time Complexity: O(n!). At row 0 you have n choices, at row 1 at most n-1, and so on.
• Space Complexity: O(n) for the sets, recursion stack, and queens array.

Where it breaks: n = 9 has 352 solutions, which is still fast. But N-Queens is a famously hard problem at large n (n = 27 is still an open research problem). The constraint caps at n = 9 for this reason.

Common Mistakes

• Checking if queens conflict by iterating over placed queens instead of using sets. Works, but O(n) per check vs O(1) with sets. The set approach is both faster and cleaner.
• Getting the diagonal formula wrong. Same diagonal: row - col is constant. Same anti-diagonal: row + col is constant. Mixing these up gives wrong conflict detection.
• Building the board inside the recursion on every call rather than only at leaf nodes. Build the board only when row == n, not at intermediate states.

Frequently Asked Questions

How many solutions does N-Queens have for small n? n=1: 1, n=4: 2, n=5: 10, n=6: 4, n=7: 40, n=8: 92, n=9: 352.

What’s the difference between N-Queens and N-Queens II? N-Queens II asks only for the count of solutions, not the boards themselves. You can solve it with the same backtracking but skip the board construction step, saving memory.

What does this test in an interview? The ability to model constraints efficiently. A candidate who iterates over placed queens to check conflicts demonstrates it works. A candidate who uses sets to get O(1) conflict detection demonstrates they’re thinking about performance.

← All Problems