N-Queens

HardBacktrackingNeetCode 150SeniorOpen on LeetCodeUpdated Nov 11, 2026

Place n queens on an n x n chessboard so that no two attack each other, meaning no two share a row, a column, or a diagonal. Return every distinct arrangement, in any order. Each arrangement is a list of n strings, one per row from top to bottom, where "Q" is a queen and "." is an empty square. If no arrangement exists, return an empty list.

Examples

n = 4 returns [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

The first solution: queens in columns 1, 3, 0 and 2.

Only two boards work for n = 4, and they mirror each other. In the first, the queens in rows 0 to 3 sit in columns 1, 3, 0 and 2, so no two share a column or a diagonal.

n = 1 returns [["Q"]]

A 1 x 1 board holds a single queen with nothing to attack, so there is exactly one solution.

n = 3 returns []

Any way of putting one queen in each row of a 3 x 3 board leaves some pair attacking along a column or diagonal, so the answer is an empty list.

Constraints

1 <= n <= 9

Hints

Hint 1

Queens attack along columns and both diagonals, what's the smallest set of checks to ensure a row is safe?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Every row holds exactly one queen, so place them one row at a time. For row r, try each column c whose column and diagonals are free: squares on one diagonal share r - c, and squares on the other share r + c. Mark all three in sets, recurse into row r + 1, then unmark them to try the next column. Reaching row n means every row has a safe queen, so build the board strings from the saved columns. Each safety check is O(1).

Time

O(n!)

Space

O(n)

Pitfall

Tracking only columns and one diagonal misses attacks along the other; you need both r - c and r + c. In Java, r - c can be negative, which is why the solution offsets it to r - c + n before indexing.

Solutions

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        int[] queens = new int[n];
        boolean[] cols = new boolean[n];
        boolean[] diag1 = new boolean[2 * n];
        boolean[] diag2 = new boolean[2 * n];
        backtrack(0, n, queens, cols, diag1, diag2, result);
        return result;
    }

    private void backtrack(int r, int n, int[] queens, boolean[] cols, boolean[] d1, boolean[] d2, List<List<String>> result) {
        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));
            }
            result.add(board);
            return;
        }
        for (int c = 0; c < n; c++) {
            if (cols[c] || d1[r + c] || d2[r - c + n]) continue;
            queens[r] = c;
            cols[c] = d1[r + c] = d2[r - c + n] = true;
            backtrack(r + 1, n, queens, cols, d1, d2, result);
            cols[c] = d1[r + c] = d2[r - c + n] = false;
        }
    }
}

class Solution:
    def solveNQueens(self, n: int):
        result = []
        queens = [-1] * n
        cols, d1, d2 = set(), set(), set()

        def backtrack(r):
            if r == n:
                board = []
                for c in queens:
                    row = ['.'] * n
                    row[c] = 'Q'
                    board.append("".join(row))
                result.append(board)
                return
            for c in range(n):
                if c in cols or (r + c) in d1 or (r - c) in d2:
                    continue
                queens[r] = c
                cols.add(c); d1.add(r + c); d2.add(r - c)
                backtrack(r + 1)
                cols.remove(c); d1.remove(r + c); d2.remove(r - c)

        backtrack(0)
        return result