LeetCode 51 – N-Queens

N-Queens is the problem people point at when they say "backtracking". It looks intimidating — place n queens on an n × n board so none attack each other, return every distinct arrangement — and then collapses into about twenty lines once you make one observation about the board.

The problem

Given n, return all distinct solutions to the n-queens puzzle. Each solution is the board drawn as strings, 'Q' for a queen and '.' for an empty square. Queens attack along rows, columns and both diagonals.

n = 4  ->  [[".Q..",        ["..Q.",
             "...Q",         "Q...",
             "Q...",         "...Q",
             "..Q."],        ".Q.."]]

n = 1  ->  [["Q"]]
n = 2  ->  []          no arrangement exists
n = 3  ->  []

The observation that shrinks the board

The naive framing is "choose n squares out of n²", which for n = 8 is 4.4 billion combinations. But queens attack along rows, so every row holds exactly one queen — no more, and no fewer, because n queens have to fit into n rows.

That reframes the whole problem. You are no longer choosing squares; you are choosing, for each row in turn, which column its queen sits in. The board stops being a grid and becomes a single array:

queenAt = [1, 3, 0, 2]     row 0 -> col 1, row 1 -> col 3, ...

  . Q . .
  . . . Q
  Q . . .
  . . Q .

Say this out loud before you write anything. Going from a 2-D board to an int[n] is the entire insight, and an interviewer who sees you find it stops worrying about the rest.

Backtracking is just DFS with an undo

Walk the rows top to bottom. At each row, try every column; if the placement is legal, recurse into the next row; when the recursion returns, try the next column. Reaching row n means all n queens are placed, so record the board.

Two queens conflict if they share a column, or if they share a diagonal. The diagonal test is the one worth memorising, because it is smaller than people expect:

same column     c1 == c2
same diagonal   |r1 - r2| == |c1 - c2|

Both diagonals are covered by that single line — the absolute values handle the ↘ and ↙ directions at once. Sketch a 3×3 board and check (0,0) against (2,2), then (0,2) against (2,0). There is no need to check rows at all: the loop structure guarantees one queen per row.

Java

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> boards = new ArrayList<>();
        place(boards, new int[n], 0);
        return boards;
    }

    /** queenAt[row] is the column that row's queen occupies. Rows 0..row-1 are placed. */
    private void place(List<List<String>> boards, int[] queenAt, int row) {
        if (row == queenAt.length) {
            boards.add(render(queenAt));
            return;
        }

        for (int col = 0; col < queenAt.length; col++) {
            if (safe(queenAt, row, col)) {
                queenAt[row] = col;
                place(boards, queenAt, row + 1);
                // No explicit undo: nothing below reads queenAt[row], and the next
                // iteration overwrites it. See below for when that stops being true.
            }
        }
    }

    private boolean safe(int[] queenAt, int row, int col) {
        for (int r = 0; r < row; r++) {
            int c = queenAt[r];
            if (c == col) return false;                      // same column
            if (row - r == Math.abs(col - c)) return false;   // same diagonal
        }
        return true;
    }

    private List<String> render(int[] queenAt) {
        List<String> board = new ArrayList<>();
        for (int col : queenAt) {
            char[] row = new char[queenAt.length];
            Arrays.fill(row, '.');
            row[col] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}

The missing undo is worth a sentence out loud rather than a silent omission. safe only ever reads queenAt[0 .. row-1], so a stale value at index row can never be seen. The moment you switch to marking used columns and diagonals — the next post does exactly that — the undo becomes mandatory, because those marks are read by every deeper call.

Python

class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        boards: list[list[str]] = []
        queen_at = [0] * n            # queen_at[row] = the column its queen occupies

        def safe(row: int, col: int) -> bool:
            for r in range(row):
                c = queen_at[r]
                if c == col or row - r == abs(col - c):
                    return False
            return True

        def place(row: int) -> None:
            if row == n:
                boards.append(["." * c + "Q" + "." * (n - c - 1) for c in queen_at])
                return

            for col in range(n):
                if safe(row, col):
                    queen_at[row] = col
                    place(row + 1)

        place(0)
        return boards

Rendering a row as "." * c + "Q" + "." * (n - c - 1) is the readable way to say "dots, a queen, dots" — and building it inside the base case matters. Building board strings at every level, then throwing them away when a branch fails, is a common way to turn a fast search into a slow one.

Complexity

Row 0 has n choices, row 1 has at most n - 1 that are not in the same column, and so on — hence n! as an upper bound. The diagonal pruning cuts far below that in practice, which is why n = 8 finishes instantly despite the bound. The safe scan adds an O(n) factor per placement; the next post removes it.

Do not promise a better-than-exponential bound. There is no known polynomial algorithm here, and claiming one is worse than admitting the search is exponential.

The pattern

The shape — choose, recurse, undo — is the same one behind Combination Sum (39), Permutations (46) and Permutations II (47). What changes between them is only the legality test and what "one level deeper" means. Here a level is a row and the test is two comparisons; there a level is a position and the test is a used[] flag.

N-Queens II (52) is the same search asked to return a count instead of the boards, which changes more than it sounds like it should. Sudoku Solver (37) is this with a nastier legality test and a single answer.

What the interviewer is checking

• That you find the one-queen-per-row reduction before writing code, not after.
• |r1 - r2| == |c1 - c2| for both diagonals in one test.
• That you know why no row check is needed.
• That you can say where the undo is, or explain why this version does not need one.
• That the board strings are built at the leaf, not at every level.
• n = 2 and n = 3 return an empty list rather than crashing — "no solutions" is a valid answer, not an error.