51. N-Queens (Hard)

Problem

Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution is a placement of n queens on an n × n board such that no two queens share a row, column, or diagonal.

Each solution should be a list of strings where "Q" is a queen and "." is empty.

Example

n = 4 → [[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]]
n = 1 → [["Q"]]

LeetCode 51 · Link · Hard

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, try all n^n placements

Try every possible column for every row; filter valid placements.

from itertools import product

def solve_n_queens(n):
    result = []
    for cols in product(range(n), repeat=n):         # L1: O(n^n) outer enumeration
        if len(set(cols)) != n:
            continue                                  # L2: column conflict
        ok = True
        for r1 in range(n):
            for r2 in range(r1 + 1, n):
                if abs(cols[r1] - cols[r2]) == r2 - r1:
                    ok = False; break                 # L3: O(n²) diagonal check
            if not ok: break
        if ok:
            board = [["." if c != cols[r] else "Q" for c in range(n)] for r in range(n)]
            result.append(["".join(row) for row in board])
    return result

Complexity

Time: $O(n^n · n²)$ . Infeasible past n ≈ 7.
Space: same.

Swift

final class Solution {
    func solveNQueens(_ n: Int) -> [[String]] {
        var result: [[String]] = []
        func build(_ columns: [Int]) -> [String] { columns.map { column in String(repeating: ".", count: column) + "Q" + String(repeating: ".", count: n - column - 1) } }
        func enumerate(_ rows: [Int]) { if rows.count == n { for row in 0..<n { for other in (row + 1)..<n { if rows[row] == rows[other] || abs(rows[row] - rows[other]) == other - row { return } } }; result.append(build(rows)); return }; for column in 0..<n { enumerate(rows + [column]) } }
        enumerate([]); return result
    }
}

Approach 2: Backtracking row-by-row with linear conflict check

Place one queen per row; for each row, try each column, check conflicts by walking previously placed queens.

def solve_n_queens(n):
    result = []
    cols = [-1] * n

    def valid(r, c):
        for r2 in range(r):
            if cols[r2] == c or abs(cols[r2] - c) == r - r2:  # L1: O(r) check
                return False
        return True

    def backtrack(r):
        if r == n:
            result.append(["".join("Q" if cols[i] == j else "." for j in range(n)) for i in range(n)])
            return
        for c in range(n):
            if valid(r, c):              # L2: O(r) per column
                cols[r] = c
                backtrack(r + 1)         # L3: recurse
                cols[r] = -1

    backtrack(0)
    return result

Complexity

Time: exponential; conflict check per placement is $O(r)$ .
Space: $O(n)$ recursion + output.

Swift

final class Solution {
    func solveNQueens(_ n: Int) -> [[String]] {
        var result: [[String]] = []
        func safe(_ columns: [Int], _ column: Int) -> Bool { for (row, placed) in columns.enumerated() { let nextRow = columns.count; if placed == column || abs(placed - column) == nextRow - row { return false } }; return true }
        func search(_ columns: [Int]) { if columns.count == n { result.append(columns.map { String(repeating: ".", count: $0) + "Q" + String(repeating: ".", count: n - $0 - 1) }); return }; for column in 0..<n where safe(columns, column) { search(columns + [column]) } }
        search([]); return result
    }
}

Approach 3: Backtracking with column + diagonal sets (optimal)

Maintain three sets: used columns, used row + col diagonals (anti-diagonals), used row - col diagonals. All checks are $O(1)$ .

def solve_n_queens(n):
    result = []
    cols_used = set()
    diag1 = set()   # row + col
    diag2 = set()   # row - col
    placement = [-1] * n

    def backtrack(r):
        if r == n:
            board = ["".join("Q" if placement[i] == j else "." for j in range(n)) for i in range(n)]
            result.append(board)                      # L1: O(n²) build board
            return
        for c in range(n):
            if c in cols_used or (r + c) in diag1 or (r - c) in diag2:
                continue                              # L2: O(1) conflict check
            cols_used.add(c)                          # L3: O(1) mark column
            diag1.add(r + c)                          # L4: O(1) mark anti-diag
            diag2.add(r - c)                          # L5: O(1) mark main diag
            placement[r] = c
            backtrack(r + 1)                          # L6: recurse to next row
            cols_used.remove(c)                       # L7: O(1) unmark
            diag1.remove(r + c)
            diag2.remove(r - c)

    backtrack(0)
    return result

function solveNQueens(n: number): string[][] {
    const result: string[][] = [];
    const colsUsed = new Set<number>();
    const diag1 = new Set<number>();  // row + col
    const diag2 = new Set<number>();  // row - col
    const placement: number[] = new Array(n).fill(-1);

    function backtrack(r: number): void {
        if (r === n) {
            const board = Array.from({ length: n }, (_, i) =>
                Array.from({ length: n }, (_, j) => placement[i] === j ? 'Q' : '.').join('')
            );
            result.push(board);                       // L1: O(n^2) build board
            return;
        }
        for (let c = 0; c < n; c++) {
            if (colsUsed.has(c) || diag1.has(r + c) || diag2.has(r - c))
                continue;                             // L2: O(1) conflict check
            colsUsed.add(c);                          // L3: O(1) mark column
            diag1.add(r + c);                         // L4: O(1) mark anti-diag
            diag2.add(r - c);                         // L5: O(1) mark main diag
            placement[r] = c;
            backtrack(r + 1);                         // L6: recurse to next row
            colsUsed.delete(c);                       // L7: O(1) unmark
            diag1.delete(r + c);
            diag2.delete(r - c);
        }
    }

    backtrack(0);
    return result;
}

func solveNQueens(n int) [][]string {
    result := [][]string{}
    colsUsed := map[int]bool{}
    diag1 := map[int]bool{} // row + col
    diag2 := map[int]bool{} // row - col
    placement := make([]int, n)
    for i := range placement { placement[i] = -1 }

    var backtrack func(r int)
    backtrack = func(r int) {
        if r == n {
            board := make([]string, n)
            for i := 0; i < n; i++ {
                row := make([]byte, n)
                for j := 0; j < n; j++ {
                    if placement[i] == j { row[j] = 'Q' } else { row[j] = '.' }
                }
                board[i] = string(row) // L1: O(n^2) build board
            }
            result = append(result, board)
            return
        }
        for c := 0; c < n; c++ {
            if colsUsed[c] || diag1[r+c] || diag2[r-c] {
                continue // L2: O(1) conflict check
            }
            colsUsed[c] = true   // L3: O(1) mark column
            diag1[r+c] = true    // L4: O(1) mark anti-diag
            diag2[r-c] = true    // L5: O(1) mark main diag
            placement[r] = c
            backtrack(r + 1)     // L6: recurse to next row
            delete(colsUsed, c)  // L7: O(1) unmark
            delete(diag1, r+c)
            delete(diag2, r-c)
        }
    }

    backtrack(0)
    return result
}

Where the time goes, line by line

Variables: n = the board size.

Line	Per-call cost	Times executed	Contribution
L1 (build board)	$O(n²)$	solutions	$O(solutions · n²)$
L2 (conflict check)	$O(1)$	n per row per path	$O(n · n!)$
L3/L4/L5 (mark sets)	$O(1)$	valid placements	$O(n!)$
L6 (recurse)	$O(1)$ dispatch	$O(n!)$ nodes	$O(n!)$ ← dominates
L7 (unmark)	$O(1)$	valid placements	$O(n!)$

The recursion tree has at most n! leaves (after column pruning). Each level has at most n candidates, but the conflict sets reduce the effective branching to roughly n - row.

Complexity

Time: $O(n!)$ . Roughly n × (n-2) × (n-4) × … branches after pruning.
Space: $O(n)$ sets + $O(n)$ recursion.

Why `row + col` and `row - col`?

Cells on the same anti-diagonal share row + col (constant along the up-right direction). Cells on the same main diagonal share row - col (constant along the down-right direction). Two integers per conflict dimension suffice to make every check $O(1)$ .

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func solveNQueens(_ n: Int) -> [[String]] {
        var result: [[String]] = [], columns = Set<Int>(), positive = Set<Int>(), negative = Set<Int>()
        func search(_ row: Int, _ placed: [Int]) { if row == n { result.append(placed.map { String(repeating: ".", count: $0) + "Q" + String(repeating: ".", count: n - $0 - 1) }); return }; for column in 0..<n where !columns.contains(column) && !positive.contains(row + column) && !negative.contains(row - column) { columns.insert(column); positive.insert(row + column); negative.insert(row - column); search(row + 1, placed + [column]); columns.remove(column); positive.remove(row + column); negative.remove(row - column) } }
        search(0, []); return result
    }
}

Summary

Approach	Time	Space
Brute enumerate placements	$O(n^n · n²)$	$O(n^n)$
Row-by-row + linear check	$O(n!)$ · $O(n)$	$O(n)$
Row-by-row + conflict sets	$O(n!)$	$O(n)$

The conflict-set template is the classic N-Queens solution and the template for constraint-satisfaction problems more broadly (Sudoku solver, exact cover).

Test cases

def solve_n_queens(n):
    result = []
    cols_used = set()
    diag1 = set()
    diag2 = set()
    placement = [-1] * n
    def backtrack(r):
        if r == n:
            board = ["".join("Q" if placement[i] == j else "." for j in range(n)) for i in range(n)]
            result.append(board)
            return
        for c in range(n):
            if c in cols_used or (r + c) in diag1 or (r - c) in diag2:
                continue
            cols_used.add(c); diag1.add(r + c); diag2.add(r - c)
            placement[r] = c
            backtrack(r + 1)
            cols_used.remove(c); diag1.remove(r + c); diag2.remove(r - c)
    backtrack(0)
    return result

def _run_tests():
    # n=1: one solution
    assert solve_n_queens(1) == [["Q"]]
    # n=4: two solutions
    r4 = solve_n_queens(4)
    assert len(r4) == 2
    assert sorted(r4) == sorted([[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]])
    # n=5: 10 solutions
    assert len(solve_n_queens(5)) == 10
    # no solution for n=2 or n=3
    assert solve_n_queens(2) == []
    assert solve_n_queens(3) == []
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function solveNQueens(n: number): string[][] {
    const result: string[][] = [];
    const colsUsed = new Set<number>();
    const diag1 = new Set<number>();
    const diag2 = new Set<number>();
    const placement: number[] = new Array(n).fill(-1);
    function backtrack(r: number): void {
        if (r === n) {
            const board = Array.from({ length: n }, (_, i) =>
                Array.from({ length: n }, (_, j) => placement[i] === j ? 'Q' : '.').join('')
            );
            result.push(board);
            return;
        }
        for (let c = 0; c < n; c++) {
            if (colsUsed.has(c) || diag1.has(r + c) || diag2.has(r - c)) continue;
            colsUsed.add(c); diag1.add(r + c); diag2.add(r - c);
            placement[r] = c;
            backtrack(r + 1);
            colsUsed.delete(c); diag1.delete(r + c); diag2.delete(r - c);
        }
    }
    backtrack(0);
    return result;
}

console.assert(JSON.stringify(solveNQueens(1)) === JSON.stringify([['Q']]));
const r4 = solveNQueens(4);
console.assert(r4.length === 2);
console.assert(JSON.stringify(r4.sort()) === JSON.stringify([['.Q..','...Q','Q...','..Q.'],['..Q.','Q...','...Q','.Q..']]
    .sort()));
console.assert(solveNQueens(5).length === 10);
console.assert(solveNQueens(2).length === 0);
console.assert(solveNQueens(3).length === 0);
console.log("all tests pass");

func solveNQueens(n int) [][]string {
    result := [][]string{}
    colsUsed := map[int]bool{}
    diag1 := map[int]bool{}
    diag2 := map[int]bool{}
    placement := make([]int, n)
    for i := range placement { placement[i] = -1 }
    var backtrack func(r int)
    backtrack = func(r int) {
        if r == n {
            board := make([]string, n)
            for i := 0; i < n; i++ {
                row := make([]byte, n)
                for j := 0; j < n; j++ {
                    if placement[i] == j { row[j] = 'Q' } else { row[j] = '.' }
                }
                board[i] = string(row)
            }
            result = append(result, board)
            return
        }
        for c := 0; c < n; c++ {
            if colsUsed[c] || diag1[r+c] || diag2[r-c] { continue }
            colsUsed[c] = true; diag1[r+c] = true; diag2[r-c] = true
            placement[r] = c
            backtrack(r + 1)
            delete(colsUsed, c); delete(diag1, r+c); delete(diag2, r-c)
        }
    }
    backtrack(0)
    return result
}

Hash Tables, columns and diagonals as $O(1)$ sets
Arrays, the board representation

Backtracking, search-tree tactics for exploring choices, undoing state, and pruning invalid branches.
Bitmask State, compact-state tactics for representing chosen items, visited sets, and small DP dimensions as integer masks.
Constraint Search, pruned search tactics for problems where each choice must satisfy local and global constraints.
Permutations, ordering tactics for generating arrangements where the same items in a different order are different answers.

51. N-Queens (Hard)

Problem

Try it yourself

Approach 1: Brute force, try all n^n placements

Approach 2: Backtracking row-by-row with linear conflict check

Approach 3: Backtracking with column + diagonal sets (optimal)

Why row + col and row - col?

Summary

Test cases

Related data structures

Related concepts

Why `row + col` and `row - col`?