LeetEye LeetEye
Hard Backtracking ~5 min

N-Queens

backtracking n-queens

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.

Examples

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

Place one queen per row. Track which columns and diagonals are occupied.

Row by row: for each column, check if column, (row-col), and (row+col) are free. Place queen, recurse, backtrack. Found when row == n.

How to Approach This Problem

Pattern Recognition: When you see keywords like n-queens backtracking, think Backtracking.

Step-by-Step Reasoning

1 A queen can attack another queen if they share:
Answer: Any of the above
Queens attack horizontally, vertically, and diagonally.
2 Since each queen attacks its entire row, each row can have:
Answer: Exactly 1 queen
More than one queen in a row = they attack each other. We need exactly n queens in n rows.
3 To ensure no two queens share a column:
Answer: Track which columns are used
Keep a set of occupied columns. Skip columns already used.
4 Cells on the same diagonal share:
Answer: Both A and B identify the two diagonal directions
(r-c) is constant on one diagonal, (r+c) on the other.
5 We backtrack when:
Answer: No column in current row is safe
If no valid placement in current row, previous choices were wrong. Undo and try different.
6 We found a valid solution when:
Answer: All n rows have a queen
If we successfully place a queen in each of n rows, we have a valid configuration.

Solution

def solveNQueens(n: int) -> List[List[str]]:
    result = []
    cols = set()
    pos_diag = set()  # r + c
    neg_diag = set()  # r - c
    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 pos_diag or (row - col) in neg_diag:
                continue
            
            cols.add(col)
            pos_diag.add(row + col)
            neg_diag.add(row - col)
            board[row][col] = 'Q'
            
            backtrack(row + 1)
            
            cols.remove(col)
            pos_diag.remove(row + col)
            neg_diag.remove(row - col)
            board[row][col] = '.'
    
    backtrack(0)
    return result

Complexity Analysis

Time O(n!)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Backtracking problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye