Backtracking — N-Queens

↗ LeetCode: N-Queens · Hard · pattern chapter →

Asked atMetaAmazonGoogleMicrosoftApple

Place n queens on an n × n board so no two attack each other. Return all distinct solutions.

Example — n=4 → 2 solutions

Constraints — 1 ≤ n ≤ 9.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Brute force (all n^n placements)

Intuition. Try every placement of n queens in the n² cells → C(n², n) combinations. Filter valid ones.

Complexity — C(64, 8) ≈ 4·10⁹ for n=8. TLE.

---

Approach 2 — Row-by-row backtracking with O(n) validity check

Insight. Because there's exactly one queen per row, iterate rows and place a queen in each. For each row r, try columns c = 0..n-1; validate that (r, c) doesn't share a column, main-diagonal, or anti-diagonal with any placed queen.

List<List<String>> solveNQueensSlow(int n) {
    List<List<String>> res = new ArrayList<>();
    int[] queens = new int[n];  // queens[r] = column
    solve(0, n, queens, res);
    return res;
}
void solve(int r, int n, int[] queens, List<List<String>> res) {
    if (r == n) { res.add(render(queens)); return; }
    for (int c = 0; c < n; c++) {
        boolean ok = true;
        for (int i = 0; i < r; i++)
            if (queens[i] == c || Math.abs(queens[i] - c) == r - i) { ok = false; break; }
        if (ok) { queens[r] = c; solve(r + 1, n, queens, res); }
    }
}

Complexity — Time O(n! · n) (n! partial trees × O(n) check); Space O(n) recursion.

---

Approach 3 — Backtracking with bitset conflict tracking

Insight from row-by-row. The validity check is O(n) — but conflict membership is really about sets (which columns/diagonals are taken). Track them incrementally with three boolean sets: cols, mainDiag (r + c), antiDiag (r - c + n - 1). O(1) check per placement.

Trap. Two bitsets by r - c and r + c — swapping them rejects valid boards.

List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    int[] queens = new int[n];
    boolean[] cols = new boolean[n];
    boolean[] main = new boolean[2 * n - 1];   // r + c
    boolean[] anti = new boolean[2 * n - 1];   // r - c + n - 1
    solve(0, n, queens, cols, main, anti, res);
    return res;
}
void solve(int r, int n, int[] queens, boolean[] cols, boolean[] main, boolean[] anti, List<List<String>> res) {
    if (r == n) { res.add(render(queens)); return; }
    for (int c = 0; c < n; c++) {
        int m = r + c, a = r - c + n - 1;
        if (cols[c] || main[m] || anti[a]) continue;
        cols[c] = main[m] = anti[a] = true;
        queens[r] = c;
        solve(r + 1, n, queens, cols, main, anti, res);
        cols[c] = main[m] = anti[a] = false;
    }
}

Execution Trace

Bitset backtracking — n=4

Step 1 / 5row 0 → col 0

Complexity — Time O(n!); Space O(n). Constant-factor faster than Approach 2 because validation is O(1) per cell.

---

Try it yourself

Complexity summary

Approach	Time	Space
All placements	O(C(n², n))	O(n)
Row backtracking, O(n) check	O(n! · n)	O(n)
Row backtracking, bitset O(1) check	O(n!)	O(n)

When to use which

• Just needs solutions → bitset backtracking.
• Interviewer probes memoization → NP-complete; no polynomial memo exists (state = full board history).

✨AI Study CompanionBeta

Related problems (same ladder applies)

• N-Queens II — count solutions only
• Sudoku Solver — same backtracking, three bitset dimensions (row/col/box)
• Permutations — swap-in-place backtracking
• Subsets — start-index backtracking

Was this page helpful?