Problem 13.9 · BacktrackingHard

N-Queens

What it teaches: Place one queen per row and prune with sets of used columns and diagonals for O(1) attack checks.

Practise it on judges as “N-Queens”.

The problem

Place n queens on an n × n board so that no two attack each other (same row, column or diagonal). Return all distinct boards, each as a list of strings with 'Q' and '.'.

Example 1

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

Constraints

1 ≤ n ≤ 9

Pattern clues in the wording

→ Constraint puzzle
→ One choice per row

These clues point to Backtracking: Build a candidate one choice at a time; when a choice can't lead to an answer, undo it and try the next.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 4	[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
2	n = 1	[["Q"]]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Row-by-row backtracking with attack sets · O(n!) roughly

Row-by-row backtracking with attack sets

Time O(n!) roughly Space O(n)

dfs(row): for each column c not in cols, diag (r − c) or anti (r + c), place, recurse on row + 1, remove. Record when row == n.

Approach 1

import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> out = new ArrayList<>();
        int[] queenCol = new int[n];
        dfs(0, n, queenCol, new boolean[n], new boolean[2 * n], new boolean[2 * n], out);
        return out;
    }

    private void dfs(int r, int n, int[] q, boolean[] cols, boolean[] diag, boolean[] anti, List<List<String>> out) {
        if (r == n) {
            List<String> board = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                char[] row = new char[n];
                Arrays.fill(row, '.');
                row[q[i]] = 'Q';
                board.add(new String(row));
            }
            out.add(board);
            return;
        }
        for (int c = 0; c < n; c++) {
            if (cols[c] || diag[r - c + n] || anti[r + c]) continue;
            q[r] = c;
            cols[c] = diag[r - c + n] = anti[r + c] = true;
            dfs(r + 1, n, q, cols, diag, anti, out);
            cols[c] = diag[r - c + n] = anti[r + c] = false;
        }
    }
}

Verdict: Pruning cuts the search to a few thousand nodes for n = 8.

Before you submit

Edge cases and common mistakes

Test these inputs

n = 1 (one board)
n = 2 and 3 (no solution)

Mistakes people make

Negative indexes for r − c (offset by n).
Forgetting to clear the three markers.

Interview

Follow-up questions

How would you only count solutions, faster?

Command Palette

The problem

Approaches

Row-by-row backtracking with attack sets

Edge cases and common mistakes

Follow-up questions