Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

N-Queens

HARDProblemSolveExternal Links

Description

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

A queen can attack any piece that lies on the same row, the same column, or the same diagonal (both directions). Therefore, a valid arrangement must ensure that every queen occupies a unique row, a unique column, and a unique diagonal in each direction.

Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution is represented as a list of n strings, where each string has length n. In every string, the character 'Q' marks a queen and '.' marks an empty square. You may return the solutions in any order.

4×4 chessboard showing a valid N Queens placement with queens at row 0 col 1, row 1 col 3, row 2 col 0, row 3 col 2, with attack lines showing no conflicts
4×4 chessboard showing a valid N Queens placement with queens at row 0 col 1, row 1 col 3, row 2 col 0, row 3 col 2, with attack lines showing no conflicts

Examples

Example 1

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Explanation: There are exactly two distinct ways to place 4 queens on a 4×4 board:

Solution 1:

. Q . .
. . . Q
Q . . .
. . Q .

Queens sit at (0,1), (1,3), (2,0), (3,2). No two share a row, column, or diagonal.

Solution 2:

. . Q .
Q . . .
. . . Q
. Q . .

Queens sit at (0,2), (1,0), (2,3), (3,1). Again, all constraints are satisfied.

Example 2

Input: n = 1

Output: [["Q"]]

Explanation: With only one row and one column, the single queen is placed on the only available square. There are no other queens to conflict with.

Example 3

Input: n = 2

Output: []

Explanation: On a 2×2 board, placing a queen at any corner immediately attacks both remaining non-corner squares (via diagonal and row/column). No arrangement of 2 queens can avoid conflicts. The same holds for n = 3.

Constraints

  • 1 ≤ n ≤ 9

Editorial

Brute Force - Backtracking with Linear Safety Check

Intuition

Because every valid solution has exactly one queen per row, we can build solutions one row at a time. For row 0 we try every column; for each choice that does not conflict with previously placed queens we move on to row 1, and so on.

When we reach a row where no column is safe, we have hit a dead end. We undo our last placement ("backtrack") and try the next column in the previous row. This systematic explore-and-undo strategy is called backtracking.

To decide whether a candidate cell is safe, we scan every queen that has already been placed:

  • Same column? → conflict
  • Same diagonal? (the absolute difference of rows equals the absolute difference of columns) → conflict

Because we place exactly one queen per row, a row conflict is impossible, so we only need the column and diagonal checks. Scanning all previously placed queens costs up to O(n) per candidate cell.

Step-by-Step Explanation

Let's trace through the backtracking algorithm with n = 4. We place queens row by row and scan existing queens to check safety.

Step 1: Start with an empty 4×4 board. Begin placing queens from row 0.

Step 2: Row 0 — try column 0. No queens exist yet, so (0,0) is trivially safe. Place a queen at (0,0).

Step 3: Row 1 — try column 0. Scan queens: (0,0) is in column 0. Column conflict! Skip.

Step 4: Row 1 — try column 1. Scan queens: (0,0) → |0−1| = 1 and |0−1| = 1, so the cell is on the same diagonal. Diagonal conflict! Skip.

Step 5: Row 1 — try column 2. Scan queens: (0,0) → different column, |0−1| ≠ |0−2|. No conflict. Place queen at (1,2).

Step 6: Row 2 — try all columns. Col 0: column conflict with (0,0). Col 1: diagonal conflict with (1,2). Col 2: column conflict with (1,2). Col 3: diagonal conflict with (1,2). Every column is blocked. Dead end!

Step 7: Backtrack — remove queen from (1,2). Return to row 1.

Step 8: Row 1 — try column 3. Scan: (0,0) → different column, |0−1| ≠ |0−3|. Safe! Place queen at (1,3).

Step 9: Row 2 — column 0: column conflict with (0,0). Column 1: no column or diagonal conflict with either queen. Safe! Place queen at (2,1).

Step 10: Row 3 — Col 0: column conflict with (0,0). Col 1: column conflict with (2,1). Col 2: diagonal conflict with (2,1). Col 3: column conflict with (1,3). All blocked. Dead end!

Step 11: Backtrack — remove queen from (2,1). Remaining columns in row 2 also fail: (2,2) diagonal with (0,0), (2,3) column with (1,3). Dead end in row 2.

Step 12: Backtrack — remove queen from (1,3). Row 1 is fully exhausted while queen sits at (0,0).

Step 13: Backtrack — remove queen from (0,0). Try next column in row 0.

Step 14: Row 0 — try column 1. Safe. Place queen at (0,1).

Step 15: Row 1 — column 0: diagonal with (0,1). Col 1: same column. Col 2: diagonal with (0,1). Column 3: |0−1| = 1, |1−3| = 2, no conflict. Safe! Place queen at (1,3).

Step 16: Row 2 — column 0: no column or diagonal conflict with either queen. Safe! Place queen at (2,0).

Step 17: Row 3 — column 2: scan (0,1) → |0−3| ≠ |1−2|, (1,3) → |1−3| ≠ |3−2|, (2,0) → |2−3| ≠ |0−2|. No conflicts. Safe! Place queen at (3,2).

Step 18: All 4 queens placed. Record solution: [".Q..", "...Q", "Q...", "..Q."].

N Queens — Backtracking with Row-by-Row Placement — Watch how the algorithm places queens row by row, scanning existing queens for conflicts, and backtracks whenever a dead end is reached.

Algorithm

  1. Create an n × n board filled with '.'.
  2. Define a helper isSafe(board, row, col) that scans all rows above row to check:
    • Is there a queen in the same column?
    • Is there a queen on the upper-left diagonal?
    • Is there a queen on the upper-right diagonal?
  3. Define backtrack(row):
    • Base case: if row == n, copy the board into the result list.
    • For each col from 0 to n − 1:
      • If isSafe(board, row, col), place 'Q' at (row, col).
      • Recurse: backtrack(row + 1).
      • Remove the queen (set back to '.') — this is the backtrack step.
  4. Call backtrack(0) and return the collected results.

Code

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.'));
        backtrack(board, 0, result);
        return result;
    }

private:
    bool isSafe(vector<string>& board, int row, int col) {
        int n = board.size();
        // Check the same column in all rows above
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // Check upper-left diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // Check upper-right diagonal
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }

    void backtrack(vector<string>& board, int row,
                   vector<vector<string>>& result) {
        if (row == (int)board.size()) {
            result.push_back(board);
            return;
        }
        for (int col = 0; col < (int)board.size(); col++) {
            if (isSafe(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(board, row + 1, result);
                board[row][col] = '.';
            }
        }
    }
};
class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        result: list[list[str]] = []
        board = [['.' for _ in range(n)] for _ in range(n)]

        def is_safe(row: int, col: int) -> bool:
            # Check same column above
            for i in range(row):
                if board[i][col] == 'Q':
                    return False
            # Check upper-left diagonal
            i, j = row - 1, col - 1
            while i >= 0 and j >= 0:
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j -= 1
            # Check upper-right diagonal
            i, j = row - 1, col + 1
            while i >= 0 and j < n:
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j += 1
            return True

        def backtrack(row: int) -> None:
            if row == n:
                result.append([''.join(r) for r in board])
                return
            for col in range(n):
                if is_safe(row, col):
                    board[row][col] = 'Q'
                    backtrack(row + 1)
                    board[row][col] = '.'

        backtrack(0)
        return result
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(board, 0, result);
        return result;
    }

    private boolean isSafe(char[][] board, int row, int col) {
        int n = board.length;
        // Check same column above
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // Check upper-left diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // Check upper-right diagonal
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }

    private void backtrack(char[][] board, int row,
                           List<List<String>> result) {
        if (row == board.length) {
            List<String> solution = new ArrayList<>();
            for (char[] r : board) solution.add(new String(r));
            result.add(solution);
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (isSafe(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(board, row + 1, result);
                board[row][col] = '.';
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n! × n)

The backtracking tree has at most n choices in row 0, roughly n − 2 in row 1 (columns and diagonals eliminate some), and so on. This gives approximately n × (n−2) × (n−4) × … ≈ O(n!) nodes in the recursion tree. At each node the isSafe function scans up to n previously placed queens, adding an O(n) factor. Total: O(n! × n).

Space Complexity: O(n²)

The n × n board itself requires O(n²) space. The recursion stack goes at most n levels deep, contributing O(n). Dominant term: O(n²).

Why This Approach Is Not Efficient

The backtracking strategy itself is already efficient in terms of exploration — it prunes impossible branches early. However, the safety check is the bottleneck in this implementation.

Every time we consider placing a queen, isSafe scans up to n rows to verify the column and both diagonals. This O(n) scan is performed at every candidate cell across all levels of recursion, adding a multiplicative O(n) factor to the total time.

With n up to 9 this overhead is small in absolute terms, but the repeated scanning is conceptually wasteful: we keep re-checking the same columns and diagonals that have not changed since the last placement.

Key insight: If we record which columns and diagonals are already occupied using auxiliary data structures, we can answer the safety question in O(1) per candidate instead of O(n). This eliminates the extra factor of n from the time complexity.

Optimal Approach - Backtracking with Column and Diagonal Hash Sets

Intuition

The exploration order is identical to the brute force — we still place queens row by row and backtrack on dead ends. The improvement is entirely in how quickly we decide whether a cell is safe.

We maintain three sets:

  1. cols — the set of column indices that already hold a queen.
  2. posDiag — the set of positive-diagonal identifiers. Every cell on the same top-left → bottom-right diagonal shares the same value of row + col.
  3. negDiag — the set of negative-diagonal identifiers. Every cell on the same top-right → bottom-left diagonal shares the same value of row − col.

To check whether cell (r, c) is safe we simply ask:

  • Is c in cols?
  • Is r + c in posDiag?
  • Is r − c in negDiag?

All three lookups are O(1) in a hash set. When we place a queen we add entries to the three sets; when we backtrack we remove them. The exploration tree is the same, but each node is processed in O(1) instead of O(n).

Step-by-Step Explanation

Let's trace through with n = 4, tracking the three sets at each decision.

Step 1: Initialize: cols = {}, posDiag = {}, negDiag = {}. Empty board.

Step 2: Row 0, column 0. Check: 0 ∉ cols, 0+0=0 ∉ posDiag, 0−0=0 ∉ negDiag → safe in O(1). Place queen. Update sets: cols={0}, posDiag={0}, negDiag={0}.

Step 3: Row 1, column 0. Check: 0 ∈ cols → blocked instantly. No need to check diagonals.

Step 4: Row 1, column 1. Check: 1 ∉ cols ✓, 1+1=2 ∉ posDiag ✓, 1−1=0 ∈ negDiag → blocked! The set told us immediately that diagonal 0 is occupied.

Step 5: Row 1, column 2. Check: 2 ∉ cols ✓, 1+2=3 ∉ posDiag ✓, 1−2=−1 ∉ negDiag ✓ → safe! Place queen. cols={0,2}, posDiag={0,3}, negDiag={0,−1}.

Step 6: Row 2, all four columns blocked by sets. Col 0: 0 ∈ cols. Col 1: 2+1=3 ∈ posDiag. Col 2: 2 ∈ cols. Col 3: 2−3=−1 ∈ negDiag. Dead end.

Step 7: Backtrack from (1,2). Remove from sets: cols={0}, posDiag={0}, negDiag={0}.

Step 8: Row 1, column 3. Check: 3 ∉ cols ✓, 1+3=4 ∉ posDiag ✓, 1−3=−2 ∉ negDiag ✓ → safe! cols={0,3}, posDiag={0,4}, negDiag={0,−2}.

Step 9: Row 2, column 1. Check: 1 ∉ cols ✓, 2+1=3 ∉ posDiag ✓, 2−1=1 ∉ negDiag ✓ → safe! cols={0,1,3}, posDiag={0,3,4}, negDiag={0,−2,1}.

Step 10: Row 3 all blocked. Col 0: 0 ∈ cols. Col 1: 1 ∈ cols. Col 2: 3−2=1 ∈ negDiag. Col 3: 3 ∈ cols. Dead end.

Step 11: Backtrack from (2,1). Remaining row 2 candidates: (2,2) → 2+2=4 ∈ posDiag, (2,3) → 3 ∈ cols. All fail. Backtrack from (1,3). Row 1 exhausted. Backtrack from (0,0).

Step 12: Row 0, column 1. Safe. cols={1}, posDiag={1}, negDiag={−1}.

Step 13: Row 1, column 3. 3 ∉ cols, 1+3=4 ∉ posDiag, 1−3=−2 ∉ negDiag → safe. cols={1,3}, posDiag={1,4}, negDiag={−1,−2}.

Step 14: Row 2, column 0. 0 ∉ cols, 2+0=2 ∉ posDiag, 2−0=2 ∉ negDiag → safe. cols={0,1,3}, posDiag={1,2,4}, negDiag={−1,−2,2}.

Step 15: Row 3, column 2. 2 ∉ cols, 3+2=5 ∉ posDiag, 3−2=1 ∉ negDiag → safe! Place queen.

Step 16: All 4 queens placed. Solution: [".Q..","...Q","Q...","..Q."].

N Queens — O(1) Safety Check with Column & Diagonal Sets — Watch how three hash sets (cols, posDiag, negDiag) let us accept or reject each candidate in constant time, eliminating the linear scan of the brute force.

Algorithm

  1. Create an n × n board filled with '.'.
  2. Initialize three empty sets: cols, posDiag, negDiag.
  3. Define backtrack(row):
    • Base case: if row == n, copy the board into the result list.
    • For each col from 0 to n − 1:
      • If col ∈ cols or (row + col) ∈ posDiag or (row − col) ∈ negDiag, skip this column.
      • Otherwise, place 'Q' at (row, col) and add entries to all three sets.
      • Recurse: backtrack(row + 1).
      • Remove the queen and delete entries from the three sets.
  4. Call backtrack(0) and return results.

Code

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.'));
        unordered_set<int> cols, posDiag, negDiag;
        backtrack(board, 0, cols, posDiag, negDiag, result);
        return result;
    }

private:
    void backtrack(vector<string>& board, int row,
                   unordered_set<int>& cols,
                   unordered_set<int>& posDiag,
                   unordered_set<int>& negDiag,
                   vector<vector<string>>& result) {
        if (row == (int)board.size()) {
            result.push_back(board);
            return;
        }
        for (int col = 0; col < (int)board.size(); col++) {
            if (cols.count(col) || posDiag.count(row + col)
                || negDiag.count(row - col))
                continue;

            board[row][col] = 'Q';
            cols.insert(col);
            posDiag.insert(row + col);
            negDiag.insert(row - col);

            backtrack(board, row + 1, cols, posDiag, negDiag, result);

            board[row][col] = '.';
            cols.erase(col);
            posDiag.erase(row + col);
            negDiag.erase(row - col);
        }
    }
};
class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        result: list[list[str]] = []
        board = [['.' for _ in range(n)] for _ in range(n)]
        cols: set[int] = set()
        pos_diag: set[int] = set()   # row + col
        neg_diag: set[int] = set()   # row - col

        def backtrack(row: int) -> None:
            if row == n:
                result.append([''.join(r) for r in board])
                return
            for col in range(n):
                if (col in cols
                        or (row + col) in pos_diag
                        or (row - col) in neg_diag):
                    continue

                board[row][col] = 'Q'
                cols.add(col)
                pos_diag.add(row + col)
                neg_diag.add(row - col)

                backtrack(row + 1)

                board[row][col] = '.'
                cols.remove(col)
                pos_diag.remove(row + col)
                neg_diag.remove(row - col)

        backtrack(0)
        return result
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        Set<Integer> cols = new HashSet<>();
        Set<Integer> posDiag = new HashSet<>();
        Set<Integer> negDiag = new HashSet<>();
        backtrack(board, 0, cols, posDiag, negDiag, result);
        return result;
    }

    private void backtrack(char[][] board, int row,
                           Set<Integer> cols,
                           Set<Integer> posDiag,
                           Set<Integer> negDiag,
                           List<List<String>> result) {
        if (row == board.length) {
            List<String> solution = new ArrayList<>();
            for (char[] r : board) solution.add(new String(r));
            result.add(solution);
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (cols.contains(col) || posDiag.contains(row + col)
                || negDiag.contains(row - col))
                continue;

            board[row][col] = 'Q';
            cols.add(col);
            posDiag.add(row + col);
            negDiag.add(row - col);

            backtrack(board, row + 1, cols, posDiag, negDiag, result);

            board[row][col] = '.';
            cols.remove(col);
            posDiag.remove(row + col);
            negDiag.remove(row - col);
        }
    }
}

Complexity Analysis

Time Complexity: O(n!)

The recursion tree is identical to the brute force — approximately n! nodes because each successive row has fewer valid columns. The critical improvement is that each node now does O(1) work for the safety check (three hash set lookups) instead of O(n). This removes the extra factor, giving O(n!) total.

Space Complexity: O(n)

The three hash sets (cols, posDiag, negDiag) each store at most n entries, so they consume O(n) space in total. The recursion stack is also O(n) deep. The board itself costs O(n²) for constructing the output strings, but the auxiliary space used by the algorithm is O(n).