#51 N-Queens

frequently reported atByteDance / TikTok Amazon Microsoft Google Meta

the problem

In plain words

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

in n = 4

out [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

in n = 1

out [["Q"]]

1 ≤ n ≤ 9

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBacktracking with constraint pruning

Exactly one queen per row, so decide one column per row. Squares on the same ↘ diagonal share row − col; on the same ↙ diagonal they share row + col.

solutions

From brute force to optimal

For each row try every column; check the column and both diagonals above by walking the board.

row == n → record the board.
For each col: if safe (O(n) scan upwards), place 'Q', recurse(row + 1), remove.

timeO(n·n!)

At most n! placements are explored, and each safety test scans up to n rows.

spaceO(n²)

The board; recursion depth is n.

javajava.util.*

1class Solution {2    public List<List<String>> solveNQueens(int n) {3        char[][] board = new char[n][n];4        for (char[] row : board) Arrays.fill(row, '.');5        List<List<String>> result = new ArrayList<>();6        place(board, 0, result);7        return result;8    }9 10    private void place(char[][] board, int row, List<List<String>> result) {11        int n = board.length;12        if (row == n) {13            List<String> snapshot = new ArrayList<>();14            for (char[] r : board) snapshot.add(new String(r));15            result.add(snapshot);16            return;17        }18        for (int col = 0; col < n; col++) {19            if (!safe(board, row, col)) continue;20            board[row][col] = 'Q';21            place(board, row + 1, result);22            board[row][col] = '.';23        }24    }25 26    /** Only rows above can hold queens: check up, up-left and up-right. O(n). */27    private boolean safe(char[][] board, int row, int col) {28        for (int r = row - 1, d = 1; r >= 0; r--, d++) {29            if (board[r][col] == 'Q') return false;30            if (col - d >= 0 && board[r][col - d] == 'Q') return false;31            if (col + d < board.length && board[r][col + d] == 'Q') return false;32        }33        return true;34    }35}

Keep cols[c], diag[row − col + n − 1] and anti[row + col] as booleans; a square is safe iff all three are false.

row == n → record.
For each col: skip if any of the three is true.
Place: set all three true; recurse; remove: set them false.

timeO(n!)

Row r has at most n − r safe columns, so ≤ n! placements, each O(1) (plus O(n²) per recorded board).

spaceO(n²)

The board for output; the three arrays are O(n) and recursion depth is n.

javajava.util.*

1class Solution {2    private boolean[] cols, diag, anti;   // diag: row - col + n - 1, anti: row + col3    private char[][] board;4    private List<List<String>> result;5 6    public List<List<String>> solveNQueens(int n) {7        cols = new boolean[n];8        diag = new boolean[2 * n - 1];9        anti = new boolean[2 * n - 1];10        board = new char[n][n];11        for (char[] row : board) Arrays.fill(row, '.');12        result = new ArrayList<>();13        place(0, n);14        return result;15    }16 17    private void place(int row, int n) {18        if (row == n) { // every row has a queen19            List<String> snapshot = new ArrayList<>();20            for (char[] r : board) snapshot.add(new String(r));21            result.add(snapshot);22            return;23        }24        for (int col = 0; col < n; col++) {25            if (cols[col] || diag[row - col + n - 1] || anti[row + col]) continue; // O(1) attack test26            board[row][col] = 'Q';27            cols[col] = diag[row - col + n - 1] = anti[row + col] = true;28            place(row + 1, n);29            board[row][col] = '.';30            cols[col] = diag[row - col + n - 1] = anti[row + col] = false;31        }32    }33}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    private boolean[] cols, diag, anti;   // diag: row - col + n - 1, anti: row + col3    private char[][] board;4    private List<List<String>> result;5 6    public List<List<String>> solveNQueens(int n) {7        cols = new boolean[n];8        diag = new boolean[2 * n - 1];9        anti = new boolean[2 * n - 1];10        board = new char[n][n];11        for (char[] row : board) Arrays.fill(row, '.');12        result = new ArrayList<>();13        place(0, n);14        return result;15    }16 17    private void place(int row, int n) {18        if (row == n) { // every row has a queen19            List<String> snapshot = new ArrayList<>();20            for (char[] r : board) snapshot.add(new String(r));21            result.add(snapshot);22            return;23        }24        for (int col = 0; col < n; col++) {25            if (cols[col] || diag[row - col + n - 1] || anti[row + col]) continue; // O(1) attack test26            board[row][col] = 'Q';27            cols[col] = diag[row - col + n - 1] = anti[row + col] = true;28            place(row + 1, n);29            board[row][col] = '.';30            cols[col] = diag[row - col + n - 1] = anti[row + col] = false;31        }32    }33}

in the room

How to say it in the interview

talk track

"One queen per row removes the row constraint entirely; I only choose columns."
Derive the diagonal ids on a 3×3 sketch: row − col is constant on ↘, row + col on ↙. Offset row − col by n − 1 so it's a valid index.
Mention the answer counts (n = 4 → 2, n = 8 → 92) as sanity checks.

traps

Using row - col as an index without the + n - 1 offset (negative index).
Forgetting to clear the three flags when removing a queen.

what they ask next

Follow-ups

N-Queens II (LC 52) — just the count?

Same search, return a counter instead of boards. Bitmasks for the three sets make it very fast — it's the next problem.

Sudoku Solver (LC 37)?

Same pattern: pick an empty cell, try digits 1–9 that aren't in its row/column/box tables, recurse, undo. Return true at the first full board — see the last problem.

before you submit

Edge cases to test

n = 1 → [["Q"]].
n = 2 and n = 3 have no solution → [].
n = 9 → 352 boards, the maximum.

practise next