Start practising

N-Queens

Hard Recursion & Backtracking 2D Matrix Original on LeetCode

N-Queens is a hard recursion & backtracking problem solved with the 2d matrix pattern. The best approach, optimal (backtracking with o(1) conflict sets), runs in O(n!) time and O(n²) space. Below are 2 approaches in Java, from backtracking with board scanning up.

Problem

Place n queens on an n × n chessboard so that no two queens attack each other (same row, column or diagonal). Return every distinct board, with Q for a queen and . for an empty square.

Examples

Example 1

Input
n = 4
Output
[[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]]

Example 2

Input
n = 1
Output
[["Q"]]

Constraints

  • 1 <= n <= 9

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Backtracking with board scanningO(n! · n)O(n²)
Optimal (backtracking with O(1) conflict sets)O(n!)O(n²)

1Backtracking with board scanning

TimeO(n! · n)Roughly n! placements, each checked in O(n).
SpaceO(n²)

Place a queen row by row. Before placing, scan the column and both diagonals above for another queen.

  1. For each column in the current row, check safety by scanning upward.
  2. Place, recurse to the next row, remove.
Java
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> out = new ArrayList<>();
        char[][] b = new char[n][n];
        for (char[] row : b) Arrays.fill(row, '.');
        place(b, 0, out);
        return out;
    }

    private void place(char[][] b, int r, List<List<String>> out) {
        int n = b.length;
        if (r == n) {
            List<String> board = new ArrayList<>();
            for (char[] row : b) board.add(new String(row));
            out.add(board);
            return;
        }
        for (int c = 0; c < n; c++) {
            if (!safe(b, r, c)) continue;
            b[r][c] = 'Q';
            place(b, r + 1, out);
            b[r][c] = '.';
        }
    }

    private boolean safe(char[][] b, int r, int c) {
        for (int i = r - 1, d = 1; i >= 0; i--, d++) {
            if (b[i][c] == 'Q') return false;
            if (c - d >= 0 && b[i][c - d] == 'Q') return false;
            if (c + d < b.length && b[i][c + d] == 'Q') return false;
        }
        return true;
    }
}

2Optimal (backtracking with O(1) conflict sets)

TimeO(n!)
SpaceO(n²)The board; the three marker arrays are O(n).

Keep boolean arrays for used columns, used main diagonals (index r - c + n - 1) and used anti-diagonals (index r + c). A placement is safe when all three are free, checked in O(1).

  1. For each column c in row r: skip if cols[c], d1[r - c + n - 1] or d2[r + c] is set.
  2. Mark all three, place, recurse, unmark.
Java
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> out = new ArrayList<>();
        char[][] b = new char[n][n];
        for (char[] row : b) Arrays.fill(row, '.');
        place(b, 0, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1], out);
        return out;
    }

    private void place(char[][] b, int r, boolean[] cols, boolean[] d1, boolean[] d2, List<List<String>> out) {
        int n = b.length;
        if (r == n) {
            List<String> board = new ArrayList<>();
            for (char[] row : b) board.add(new String(row));
            out.add(board);
            return;
        }
        for (int c = 0; c < n; c++) {
            if (cols[c] || d1[r - c + n - 1] || d2[r + c]) continue;
            cols[c] = d1[r - c + n - 1] = d2[r + c] = true;
            b[r][c] = 'Q';
            place(b, r + 1, cols, d1, d2, out);
            b[r][c] = '.';
            cols[c] = d1[r - c + n - 1] = d2[r + c] = false;
        }
    }
}

Edge cases to test

  • n = 2 and n = 3 have no solutions

Hints

Hint 1

Place one queen per row. For each column you need O(1) checks: is the column, the main diagonal (r - c) or the anti-diagonal (r + c) taken?

FAQ

What is the best time complexity for N-Queens?

Optimal (backtracking with O(1) conflict sets) runs in O(n!) time and O(n²) extra space.

Which pattern does N-Queens use?

It is a recursion & backtracking problem that uses the 2d matrix pattern.

Is there a brute force solution for N-Queens?

Yes. Backtracking with board scanning takes O(n! · n) time and O(n²) space. Place a queen row by row.

Which edge cases should I test for N-Queens?

n = 2 and n = 3 have no solutions.