N-Queens

Difficulty: Hard Source: NeetCode

Problem

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' and '.' both indicate a queen and an empty space, respectively.

Example 1: Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Example 2: Input: n = 1 Output: [["Q"]]

Constraints:

• 1 <= n <= 9

Prerequisites

Before attempting this problem, you should be comfortable with:

• Backtracking — placing queens row by row and undoing choices when conflicts arise
• Sets for O(1) conflict detection — tracking occupied columns, diagonals, and anti-diagonals

1. Brute Force

Intuition

Place queens one per row (a queen must be in every row since we need n queens on n rows). For each row, try every column. Before placing, check if any previously placed queen attacks this position: same column, same diagonal (row - col is constant on a diagonal), or same anti-diagonal (row + col is constant on an anti-diagonal). If no conflict, place and recurse on the next row. If all n rows are filled, record the board.

Algorithm

1. Track cols, diag (row-col), anti_diag (row+col) as sets.
2. Define backtrack(row, board).
3. If row == n: record the board and return.
4. For each col in 0..n-1:
   • If col, row-col, or row+col is in any conflict set: skip.
   • Place 'Q', add to conflict sets, recurse with row+1.
   • Remove queen, remove from conflict sets.

Solution

def solveNQueens_brute(n):
    result = []
    cols = set()
    diag = set()       # row - col is constant along a diagonal
    anti_diag = set()  # row + col is constant along an anti-diagonal

    board = [['.' for _ in range(n)] for _ in range(n)]

    def backtrack(row):
        if row == n:
            result.append(["".join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag or (row + col) in anti_diag:
                continue
            board[row][col] = 'Q'
            cols.add(col)
            diag.add(row - col)
            anti_diag.add(row + col)
            backtrack(row + 1)
            board[row][col] = '.'
            cols.remove(col)
            diag.remove(row - col)
            anti_diag.remove(row + col)

    backtrack(0)
    return result


print(solveNQueens_brute(4))
# [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
print(solveNQueens_brute(1))
# [["Q"]]

Complexity

• Time: O(n!) — at most n choices for row 0, n-1 for row 1 (one column blocked), etc.
• Space: O(n) — recursion depth plus sets and board (O(n^2) for the board)

2. Backtracking with Column Array

Intuition

Instead of maintaining a 2D board, store only which column each row’s queen is placed in (queens[row] = col). Build the board strings only when a solution is found. The conflict detection is identical — sets for columns, diagonals, and anti-diagonals — but we avoid building a full board on every recursive call.

Algorithm

1. Use queens = [-1] * n to track the column placement per row.
2. Use sets for cols, diag, anti_diag.
3. On finding a complete placement, construct the board from queens.

Solution

def solveNQueens(n):
    result = []
    queens = [-1] * n  # queens[row] = col
    cols = set()
    diag = set()
    anti_diag = set()

    def build_board():
        board = []
        for row in range(n):
            board.append('.' * queens[row] + 'Q' + '.' * (n - queens[row] - 1))
        return board

    def backtrack(row):
        if row == n:
            result.append(build_board())
            return
        for col in range(n):
            if col in cols or (row - col) in diag or (row + col) in anti_diag:
                continue
            queens[row] = col
            cols.add(col)
            diag.add(row - col)
            anti_diag.add(row + col)
            backtrack(row + 1)
            queens[row] = -1
            cols.remove(col)
            diag.remove(row - col)
            anti_diag.remove(row + col)

    backtrack(0)
    return result


print(solveNQueens(4))
# [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
print(solveNQueens(1))
# [["Q"]]
print(len(solveNQueens(8)))  # 92 solutions for n=8

Complexity

• Time: O(n!) — same as brute force; set operations are O(1) each
• Space: O(n) — recursion depth; sets have at most n elements each

Common Pitfalls

Using row - col for diagonals and row + col for anti-diagonals. It’s easy to get these mixed up. A top-left-to-bottom-right diagonal has a constant row - col value. A top-right-to-bottom-left anti-diagonal has a constant row + col value. Draw a small grid and verify.

Rebuilding the board on every call. Building the board on every recursive call is wasteful. Build it only when a complete solution is found (at the base case). This is what build_board() does in the optimized version.

Not removing from sets after backtracking. Sets must be cleaned up after each recursive call. Leaving stale entries means future rows will incorrectly see those columns/diagonals as occupied.

Iterating columns incorrectly. We place exactly one queen per row. The outer loop is over rows (implicit in recursion depth), and the inner loop is over columns. Don’t iterate rows inside the loop — that leads to placing multiple queens in one row.