N-Queens: placing conflict under constraint, then pruning the tree

The 8-queens puzzle is 170 years old. The LeetCode version caps at n = 9, which means the entire constraint is: place n queens on an n-by-n board so no two share a row, column, or diagonal. That cap matters. With n <= 9 the search space is small enough that even a naive backtracker finishes instantly, but the problem still rewards understanding why the pruning works — because the same structure appears in much harder constraint-satisfaction problems.

Three things make this problem tractable. First, exactly one queen per row (n queens, n rows). Second, the diagonal conflict reduces to a single arithmetic identity. Third, backtracking lets you kill entire subtrees the moment a placement fails.

The problem

Place n queens on an n x n chessboard so that no two queens attack each other — no shared row, column, or diagonal — and return all distinct board configurations as arrays of strings, where 'Q' marks a queen and '.' marks an empty cell. Full statement: LeetCode 51.

Constraints:
- 1 <= n <= 9

What the constraint 1 <= n <= 9 actually buys you

Small n is the most important constraint here. The number of valid solutions grows fast (n=8 has 92, n=9 has 352), but the search tree itself is bounded by n!. At n=9 that is 362880 leaves before any pruning — and pruning cuts the real visited count to a tiny fraction of that.

Because n is bounded in single digits, you will never hit a stack overflow from recursion depth (max call depth is n = 9). You do not need to go iterative for safety. You do not need memoization — there is no overlapping substructure. This is a generate-all-solutions problem, and backtracking is the canonical tool for it.

The constraint also tells you that O(n!) time is completely acceptable. The solutions that push past O(n!) or add O(n^2) per placement are doing unnecessary work, but even they finish fast at these sizes. What differs between approaches is the constant inside the O(n!) envelope — specifically, how much work you spend checking each candidate placement.

Approach 1: brute force — enumerate everything, filter afterward

The naive reading: choose any n cells from n^2 cells, check if the placement is valid, keep it if it is.

from itertools import combinations
 
class Solution:
    def solveNQueens(self, n: int):
        all_positions = [(i, j) for i in range(n) for j in range(n)]
        results = []
 
        for positions in combinations(all_positions, n):
            if self._is_valid(positions):
                results.append(self._build_board(positions, n))
 
        return results
 
    def _is_valid(self, positions):
        for i in range(len(positions)):
            for j in range(i + 1, len(positions)):
                r1, c1 = positions[i]
                r2, c2 = positions[j]
                if r1 == r2 or c1 == c2 or abs(r1 - r2) == abs(c1 - c2):
                    return False
        return True
 
    def _build_board(self, positions, n):
        board = [['.' for _ in range(n)] for _ in range(n)]
        for r, c in positions:
            board[r][c] = 'Q'
        return [''.join(row) for row in board]

using System;
using System.Collections.Generic;
using System.Linq;
 
public class Solution {
    public IList<IList<string>> SolveNQueens(int n) {
        var results = new List<IList<string>>();
        var allPositions = new List<(int, int)>();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                allPositions.Add((i, j));
 
        foreach (var positions in Combinations(allPositions, n)) {
            if (IsValid(positions))
                results.Add(BuildBoard(positions, n));
        }
        return results;
    }
 
    private bool IsValid(List<(int, int)> positions) {
        for (int i = 0; i < positions.Count; i++) {
            for (int j = i + 1; j < positions.Count; j++) {
                var (r1, c1) = positions[i];
                var (r2, c2) = positions[j];
                if (r1 == r2 || c1 == c2 || Math.Abs(r1 - r2) == Math.Abs(c1 - c2))
                    return false;
            }
        }
        return true;
    }
 
    private IList<string> BuildBoard(List<(int, int)> positions, int n) {
        var board = new char[n][];
        for (int i = 0; i < n; i++) {
            board[i] = new char[n];
            Array.Fill(board[i], '.');
        }
        foreach (var (r, c) in positions)
            board[r][c] = 'Q';
        return board.Select(row => new string(row)).ToList();
    }
 
    private IEnumerable<List<(int, int)>> Combinations(List<(int, int)> src, int k) {
        if (k == 0) { yield return new List<(int, int)>(); yield break; }
        for (int i = 0; i <= src.Count - k; i++) {
            foreach (var rest in Combinations(src.GetRange(i + 1, src.Count - i - 1), k - 1)) {
                rest.Insert(0, src[i]);
                yield return rest;
            }
        }
    }
}

Time: O(C(n^2, n) * n^2). For n=8 that is C(64, 8) = 4,426,165,368 candidate sets before any pruning — each validated in O(n^2). This runs for minutes in practice. Space: O(n^2) for the board.

The point of showing this is not that you would submit it. It is that the brute force makes the constraint structure visible: the three conflict tests (same row, same column, same diagonal) are the only things that matter. Everything else is just reducing the candidates you bother to test.

Approach 2: row-by-row backtracking — one queen per row, check before placing

The key insight that unlocks everything: since we need exactly one queen per row, we can place queens row by row and never look back. Row conflict is impossible by construction. That reduces the problem to column and diagonal conflicts only, and shrinks the search tree from C(n^2, n) to at most n^n leaves (further pruned by the conflict checks).

The board is now just an array queens where queens[row] = column of the queen in that row. No 2D grid needed during search.

class Solution:
    def solveNQueens(self, n: int):
        results = []
        queens = [-1] * n
 
        def backtrack(row):
            if row == n:
                results.append(self._build_board(queens, n))
                return
            for col in range(n):
                if self._is_safe(queens, row, col):
                    queens[row] = col
                    backtrack(row + 1)
                    queens[row] = -1
 
        backtrack(0)
        return results
 
    def _is_safe(self, queens, row, col):
        for i in range(row):
            if queens[i] == col:
                return False
            if abs(queens[i] - col) == abs(i - row):
                return False
        return True
 
    def _build_board(self, queens, n):
        board = []
        for i in range(n):
            row = ['.'] * n
            row[queens[i]] = 'Q'
            board.append(''.join(row))
        return board

using System;
using System.Collections.Generic;
 
public class Solution {
    public IList<IList<string>> SolveNQueens(int n) {
        var results = new List<IList<string>>();
        var queens = new int[n];
        Array.Fill(queens, -1);
        Backtrack(0, n, queens, results);
        return results;
    }
 
    private void Backtrack(int row, int n, int[] queens, IList<IList<string>> results) {
        if (row == n) {
            results.Add(BuildBoard(queens, n));
            return;
        }
        for (int col = 0; col < n; col++) {
            if (IsSafe(queens, row, col)) {
                queens[row] = col;
                Backtrack(row + 1, n, queens, results);
                queens[row] = -1;
            }
        }
    }
 
    private bool IsSafe(int[] queens, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (queens[i] == col) return false;
            if (Math.Abs(queens[i] - col) == Math.Abs(i - row)) return false;
        }
        return true;
    }
 
    private IList<string> BuildBoard(int[] queens, int n) {
        var board = new List<string>();
        for (int i = 0; i < n; i++) {
            var row = new char[n];
            Array.Fill(row, '.');
            row[queens[i]] = 'Q';
            board.Add(new string(row));
        }
        return board;
    }
}

Time: O(n!) — the same asymptotic class as brute force, but the constant is much smaller. The _is_safe call costs O(row) for each candidate, so total work is bounded by O(n! * n). Space: O(n) for the queens array and call stack.

Hand trace: n=4, finding the first solution

The decision tree for n=4 looks like this — each level is a row, each edge is a column choice, branches marked x are pruned by conflict:

Step by step:

• row=0, col=0: place queen. queens = [0, -1, -1, -1]
• row=1, col=0: same column as row 0 -> skip
• row=1, col=1: diagonal? abs(0-1) == abs(0-1) -> yes -> skip
• row=1, col=2: column ok, diagonal abs(0-2)=2, abs(0-1)=1 -> ok. Place. queens = [0, 2, -1, -1]
• row=2: try cols 0..3. All conflict with queens at (0,0) or (1,2). Backtrack.
• row=1, col=3: column ok, diagonal abs(0-3)=3, abs(0-1)=1 -> ok. Place. queens = [0, 3, -1, -1]
• row=2, col=1: column ok, diag from row 0 abs(0-1)=1, abs(0-2)=2 ok, diag from row 1 abs(3-1)=2, abs(1-2)=1 ok. Place. queens = [0, 3, 1, -1]
• row=3, col=0..3: only col=2 passes all checks. Place. queens = [0, 3, 1, 2]
• row=4 == n -> record board. First solution: ["Q...", "...Q", ".Q..", "..Q."].

Then the search backtracks and finds the second solution queens = [1, 3, 0, 2], producing [".Q..", "...Q", "Q...", "..Q."]. Two solutions total for n=4, matching the expected output.

Approach 3: backtracking with set-based conflict tracking — O(1) per check

The bottleneck in Approach 2 is _is_safe: it loops over all previously placed queens to check column and diagonal conflicts. That loop costs O(row) per candidate. With sets tracking which columns and diagonals are occupied, each check drops to O(1).

The diagonal insight is worth internalizing. Two cells (r1, c1) and (r2, c2) share a main diagonal (top-left to bottom-right) if and only if r1 - c1 == r2 - c2. They share an anti-diagonal (top-right to bottom-left) if and only if r1 + c1 == r2 + c2. So instead of comparing each new queen against all previous queens, you track three sets — occupied columns, occupied (row - col) values, occupied (row + col) values — and a single membership test covers all three conflict types.

class Solution:
    def solveNQueens(self, n: int):
        results = []
        queens = []
        cols = set()
        diag_main = set()   # row - col is constant along a main diagonal
        diag_anti = set()   # row + col is constant along an anti-diagonal
 
        def backtrack(row):
            if row == n:
                results.append(self._build_board(queens, n))
                return
            for col in range(n):
                if col in cols or (row - col) in diag_main or (row + col) in diag_anti:
                    continue
                queens.append(col)
                cols.add(col)
                diag_main.add(row - col)
                diag_anti.add(row + col)
 
                backtrack(row + 1)
 
                queens.pop()
                cols.remove(col)
                diag_main.remove(row - col)
                diag_anti.remove(row + col)
 
        backtrack(0)
        return results
 
    def _build_board(self, queens, n):
        board = []
        for i in range(n):
            row = ['.'] * n
            row[queens[i]] = 'Q'
            board.append(''.join(row))
        return board

using System;
using System.Collections.Generic;
 
public class Solution {
    public IList<IList<string>> SolveNQueens(int n) {
        var results = new List<IList<string>>();
        var queens = new List<int>();
        var cols = new HashSet<int>();
        var diagMain = new HashSet<int>();
        var diagAnti = new HashSet<int>();
 
        Backtrack(0, n, queens, cols, diagMain, diagAnti, results);
        return results;
    }
 
    private void Backtrack(int row, int n, List<int> queens,
                           HashSet<int> cols, HashSet<int> diagMain, HashSet<int> diagAnti,
                           IList<IList<string>> results) {
        if (row == n) {
            results.Add(BuildBoard(queens, n));
            return;
        }
        for (int col = 0; col < n; col++) {
            if (cols.Contains(col) || diagMain.Contains(row - col) || diagAnti.Contains(row + col))
                continue;
 
            queens.Add(col);
            cols.Add(col);
            diagMain.Add(row - col);
            diagAnti.Add(row + col);
 
            Backtrack(row + 1, n, queens, cols, diagMain, diagAnti, results);
 
            queens.RemoveAt(queens.Count - 1);
            cols.Remove(col);
            diagMain.Remove(row - col);
            diagAnti.Remove(row + col);
        }
    }
 
    private IList<string> BuildBoard(List<int> queens, int n) {
        var board = new List<string>();
        for (int i = 0; i < n; i++) {
            var row = new char[n];
            Array.Fill(row, '.');
            row[queens[i]] = 'Q';
            board.Add(new string(row));
        }
        return board;
    }
}

Time: O(n!) for the same reason as Approach 2 — the decision tree has the same shape. But each node in the tree now costs O(1) for conflict checking instead of O(row), so the real constant is smaller. Space: O(n) for the three sets (each holds at most n entries), the queens list, and the call stack depth of n.

The diagonal arithmetic in more detail

It is worth spending one paragraph on why row - col encodes the main diagonal. Every cell on the same main diagonal satisfies row - col = constant. Draw a 4x4 grid and label each cell with its row - col value: the top-left cell is 0 - 0 = 0, the cell one right is 0 - 1 = -1, the cell one down from top-left is 1 - 0 = 1. Cells sharing a main diagonal all have the same label. The range of labels is -(n-1) to n-1, so there are exactly 2n - 1 distinct main diagonals. Same logic applies to row + col for anti-diagonals. Two queens conflict on a main diagonal if and only if they have the same row - col; on an anti-diagonal if and only if they have the same row + col.

This is exactly what Approach 2's abs(queens[i] - col) == abs(i - row) checks, but Approach 3 precomputes it into sets so the check is O(1) instead of comparing against every placed queen.

Edge cases

n=1: the single cell (0, 0) trivially passes all checks. One solution: [["Q"]]. Both approaches handle this — row=0, col=0 is placed, row=1 == n, record solution.

n=2 and n=3: no solutions exist. For n=2: placing a queen at (0,0) blocks column 0 and both diagonals; the only remaining cell in row 1 is (1,1), which is blocked by the anti-diagonal 0+0 == 1+1 ... no wait, 0+0=0 and 1+1=2, those are different. (1,0) is same column, (1,1): column ok, main diag 0-0=0 vs 1-1=0 — conflict. So (0,0) leads nowhere. Similarly for (0,1). No solutions. The backtracker just returns an empty list naturally, since every candidate placement for row 1 is blocked. No special case needed.

n=9: 352 solutions. The backtracker finds all of them in microseconds. The pruning ratio is enormous — the unpruned n^n = 387,420,489 paths shrinks to 352 valid ones.

queen at edge columns (col=0 or col=n-1): diagonal checks are asymmetric for edge columns (one anti-diagonal does not exist). The set math handles this transparently — the row - col and row + col values for edge cells are just numbers; there is no special boundary logic needed.

Approach comparison

The asymptotic difference between "O(n! * n)" and "O(n!)" matters only in aggregate over the full tree. In practice at n <= 9, both approaches are nearly instantaneous. The set version is cleaner to read once you understand the diagonal arithmetic, which is why I would write it as the default.

What I would ship and why

The set-based backtracker (Approach 3). Not because of performance at n <= 9 — anything beats brute force there, and the performance gap between Approach 2 and 3 is invisible at these sizes. I would ship Approach 3 because the three-set structure makes the conflict model explicit: one set per conflict dimension (column, main diagonal, anti-diagonal). Reading the code, you can see the three independent constraints directly. Approach 2 buries that structure inside _is_safe's loop.

The diagonal arithmetic (row - col, row + col) is worth understanding once. After that, it becomes a tool you reach for in grid-constraint problems without thinking about it.

I would not ship Approach 1 under any circumstances. C(64, 8) is too many combinations to enumerate even when n is small. Its only value is as a correctness reference to test the other implementations against.

The underlying pattern and where it transfers

N-Queens is the canonical example of backtracking on a constraint-satisfaction problem. The skeleton is: choose, check constraints, recurse, un-choose. The choose/un-choose pair is what makes it backtracking rather than plain recursion — you are modifying shared state (queens, sets) and restoring it afterward.

The three-set conflict encoding is more broadly useful than it looks. Any time you have a grid problem where you need O(1) conflict detection across multiple constraint dimensions, the (row - col) / (row + col) trick for diagonals is the first thing to reach for.

N-Queens sits in the backtracking series after Subsets, Permutations, and Combination Sum. Those problems introduced the choose/recurse/un-choose skeleton on simpler domains (number arrays, no cross-element constraints). N-Queens adds cross-element constraints — the choice at row 3 depends on what you placed at rows 0, 1, 2. That is the step up in difficulty.

N-Queens II (52) is the direct follow-on: same logic, but return the count of solutions instead of the solutions themselves. If you have this solution, 52 is a three-line change — replace results.append(self._build_board(...)) with self.count += 1.

Sudoku Solver (37) is the harder cousin. The board is 9x9 with 81 cells, rows, columns, and 3x3 boxes as constraints. The backtracking skeleton is the same; the conflict checking is more complex (3 constraint dimensions with different shapes). The same set-based approach works.

Word Search (79) adds the spatial exploration dimension — instead of placing one item per row, you walk a path through a grid. The choose/un-choose skeleton is identical; the state being undone is the visited cell marker rather than a queen placement.

Permutations (46) is simpler in one dimension (no diagonal constraints) but has the same "each element used exactly once" invariant enforced by a used set. Same structure.