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, Python, C++ and JavaScript, 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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 7 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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.
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.
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.