N-Queens

hardBacktracking391 stepsJava · Python · C++

Place n queens so none attack each other. Place one queen per row; for each row try every column not under attack. Three sets track used columns and both diagonals (r - c and r + c), so checking a square is O(1).

▶ Watch the animated trace

Traced input: n = 4 → [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]. Original problem: neetcode.io/problems/n-queens

Complexity

BestO(n!)

AverageO(n!)

WorstO(n!)

SpaceO(n)

At most n choices in the first row, n−1 in the next, and so on.

Key idea

One queen per row, so recursion depth is n.
Squares on the same ↘ diagonal share r - c; on the same ↙ diagonal they share r + c.
Add to the sets before recursing, remove after.

Common mistakes

Checking the whole board for every placement is O(n) per check.
Forgetting one of the two diagonals.

Solution

Java

List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    place(n, 0, new int[n], new HashSet<>(), new HashSet<>(), new HashSet<>(), res);
    return res;
}

void place(int n, int r, int[] queens, Set<Integer> cols, Set<Integer> diag, Set<Integer> anti, List<List<String>> res) {
    if (r == n) {
        List<String> board = new ArrayList<>();
        for (int c : queens) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[c] = 'Q';
            board.add(new String(row));
        }
        res.add(board);
        return;
    }
    for (int c = 0; c < n; c++) {
        if (cols.contains(c) || diag.contains(r - c) || anti.contains(r + c)) continue;
        queens[r] = c;
        cols.add(c);
        diag.add(r - c);
        anti.add(r + c);
        place(n, r + 1, queens, cols, diag, anti, res);
        cols.remove(c);
        diag.remove(r - c);
        anti.remove(r + c);
    }
}

Python

def solveNQueens(n: int) -> List[List[str]]:
    res, queens = [], [0] * n
    cols, diag, anti = set(), set(), set()

    def place(r: int) -> None:
        if r == n:
            res.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])
            return
        for c in range(n):
            if c in cols or r - c in diag or r + c in anti: continue
            queens[r] = c
            cols.add(c); diag.add(r - c); anti.add(r + c)
            place(r + 1)
            cols.remove(c); diag.remove(r - c); anti.remove(r + c)

    place(0)
    return res

C++

void place(int n, int r, vector<int>& queens, set<int>& cols, set<int>& diag, set<int>& anti, vector<vector<string>>& res) {
    if (r == n) {
        vector<string> board;
        for (int c : queens) {
            string row(n, '.');
            row[c] = 'Q';
            board.push_back(row);
        }
        res.push_back(board);
        return;
    }
    for (int c = 0; c < n; c++) {
        if (cols.count(c) || diag.count(r - c) || anti.count(r + c)) continue;
        queens[r] = c;
        cols.insert(c);
        diag.insert(r - c);
        anti.insert(r + c);
        place(n, r + 1, queens, cols, diag, anti, res);
        cols.erase(c);
        diag.erase(r - c);
        anti.erase(r + c);
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<int> queens(n);
    set<int> cols, diag, anti;
    place(n, 0, queens, cols, diag, anti, res);
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
n = 1 One queen, one square.	`n = 1`	`[["Q"]]`
n = 2 No arrangement works.	`n = 2`	`[]`
n = 3 No arrangement works either.	`n = 3`	`[]`