Skip to main content

51 - N-Queens

Difficulty: Hard | Pattern: Backtracking | Company tags: Amazon, Google, Microsoft

Problem Statement​

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' indicates a queen and '.' indicates an empty space.

Example (n=4):

Output: [[".Q..", "...Q", "Q...", "..Q."],
         ["..Q.", "Q...", "...Q", ".Q.."]]

There are 2 distinct solutions for 4-queens.

Constraints: 1 <= n <= 9

Key Insight: Backtracking​

Place queens row by row. For each row, try each column. A placement is valid if the new queen doesn't conflict with any already-placed queen. Three conflicts to check:

  1. Same column: col in cols
  2. Same positive diagonal (row - col is constant): (row - col) in pos_diag
  3. Same negative diagonal (row + col is constant): (row + col) in neg_diag

If valid, place the queen and recurse to the next row. If we reach row n, we've found a solution — record it.

Algorithm Flow​

Solution (Python)​

def solveNQueens(n: int) -> list[list[str]]:
    results = []
    # Track which columns and diagonals are occupied
    cols = set()
    pos_diag = set()  # row - col is constant on this diagonal
    neg_diag = set()  # row + col is constant on this diagonal
    
    board = [['.' for _ in range(n)] for _ in range(n)]
    
    def backtrack(row):
        if row == n:
            results.append([''.join(r) for r in board])
            return
        
        for col in range(n):
            if col in cols or (row - col) in pos_diag or (row + col) in neg_diag:
                continue
            
            # Place queen
            board[row][col] = 'Q'
            cols.add(col)
            pos_diag.add(row - col)
            neg_diag.add(row + col)
            
            backtrack(row + 1)
            
            # Remove queen (backtrack)
            board[row][col] = '.'
            cols.remove(col)
            pos_diag.remove(row - col)
            neg_diag.remove(row + col)
    
    backtrack(0)
    return results

Dry Run (n=4, first solution)​

Row 0: try col 1 → place Q at (0,1)
  cols={1}, pos_diag={-1}, neg_diag={1}
Row 1: try col 0 → 0-1=-1 in pos_diag? YES, skip
        try col 1 → 1 in cols? YES, skip
        try col 2 → 1-2=-1 in pos_diag? YES, skip
        try col 3 → place Q at (1,3)
  cols={1,3}, pos_diag={-1,-2}, neg_diag={1,4}
Row 2: try col 0 → place Q at (2,0)
  cols={0,1,3}, pos_diag={-1,-2,2}, neg_diag={1,2,4}
Row 3: try col 2 → place Q at (3,2)
  Valid! result = [".Q..", "...Q", "Q...", "..Q."]

Why Set-Based Diagonal Checks Work​

Queen positionSame columnPositive diagonal (row-col)Negative diagonal (row+col)
(0, 1)col=10-1 = -10+1 = 1
(1, 3)col=31-3 = -21+3 = 4
(2, 0)col=02-0 = +22+0 = 2
(3, 2)col=23-2 = +13+2 = 5

No duplicates in any set → valid placement.

Complexity​

  • Time: O(n!) in the worst case (n choices for row 0, at most n-2 for row 1, etc.)
  • Space: O(n²) for the board + O(n) for the sets

For n=9, this is fast enough. The 9-queens problem has 92 solutions.

Key Terms​

TermDefinition
BacktrackingIncrementally build a candidate solution, abandoning ("backtracking") a branch as soon as it can't lead to a valid answer.
Constraint propagationChecking a new placement against previously placed pieces before committing to it, so invalid branches are pruned early.
Diagonal encodingRepresenting the two diagonals through a cell (row, col) as row - col (positive diagonal) and row + col (negative diagonal), each constant along that diagonal.
State space treeThe implicit tree of all partial board configurations explored by the recursion; backtracking prunes subtrees that violate constraints.
BitmaskingAn optimization (used in N-Queens II) that replaces the cols/pos_diag/neg_diag sets with integer bitmasks for faster conflict checks.

FAQ​

Q1: Why use row - col and row + col instead of checking every previously placed queen directly? A: Both give O(1) conflict checks per candidate column via set/array lookup instead of O(row) comparisons against every placed queen, which matters since the search explores up to O(n!) states.

Q2: Why does placing one queen per row (instead of per cell) not lose any solutions? A: No valid solution can have two queens in the same row (they'd attack each other), so every valid board has exactly one queen per row. Fixing "one queen per row" only removes the impossible cases, not any real solutions.

Q3: How would you modify the code to just count solutions instead of returning boards (LeetCode 52)? A: Drop the board construction and the ''.join(r) step; just increment a counter when row == n. This also removes the O(n²) space for the board, leaving O(n) for the tracking sets.

Q4: What's the actual worst-case time complexity, and why is "O(n!)" only approximate? A: The true bound is tighter than n! because of early pruning from the diagonal/column checks, but n! is the standard stated bound since in the worst case (before pruning kicks in) each row can try up to n columns.

Q5: Why is n = 2 and n = 3 unsolvable (no output)? A: With only 2 or 3 rows/columns, every possible queen arrangement puts two queens on a shared row, column, or diagonal — there's no way to satisfy the constraints, so solveNQueens correctly returns an empty list.

Quick Revision​

  • Pattern: backtracking with one queen placed per row, columns tried left to right.
  • Conflict check is O(1) using three sets: cols, pos_diag (row - col), neg_diag (row + col).
  • Place queen → recurse to row + 1 → on return, remove queen and its marks (backtrack).
  • Base case: row == n means all n queens placed validly → record the board.
  • Time: O(n!) worst case; Space: O(n²) for the board + O(n) for the sets.
  • n=1 → 1 solution; n=2,3 → 0 solutions; n=4 → 2 solutions; n=9 → 92 solutions.
  • Swap board-building for a counter to get N-Queens II (LeetCode 52).
  • Bitmasks can replace the three sets for a faster constant factor.
  • 52 - N-Queens II — same backtracking core, but only count solutions instead of building boards.
  • Other classic backtracking problems on combinatorial placement/generation (e.g., permutations, subsets, combination sum) follow the same "choose → recurse → undo" template used here.