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.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle

Example 2:

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

Constraints:

1 <= n <= 9

Solution

Approach: Backtracking with Constraint Checking

The key insight is to place queens row by row, checking that each placement doesn’t attack previously placed queens.

Implementation

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result = []
        board = [['.'] * n for _ in range(n)]

        # Track columns, diagonals, and anti-diagonals under attack
        cols = set()
        diags = set()  # row - col
        anti_diags = set()  # row + col

        def backtrack(row):
            if row == n:
                result.append([''.join(row) for row in board])
                return

            for col in range(n):
                if col in cols or (row - col) in diags or (row + col) in anti_diags:
                    continue

                # Place queen
                board[row][col] = 'Q'
                cols.add(col)
                diags.add(row - col)
                anti_diags.add(row + col)

                backtrack(row + 1)

                # Remove queen
                board[row][col] = '.'
                cols.remove(col)
                diags.remove(row - col)
                anti_diags.remove(row + col)

        backtrack(0)
        return result

Complexity Analysis

Time Complexity: O(n!), where n is the board size. In the worst case, we try n positions in first row, (n-1) in second, etc.
Space Complexity: O(n²) for the board plus O(n) for recursion and sets.

Key Insights

Row-by-Row Placement: We place one queen per row, eliminating the need to check row conflicts.
Three Attack Directions: Queens attack horizontally (columns), and diagonally (two diagonal directions).
Diagonal Formulas:
- Main diagonals: cells have same (row - col) value
- Anti-diagonals: cells have same (row + col) value
Set for O(1) Checks: Using sets allows O(1) checking if a column or diagonal is under attack.
Backtracking Pattern: Try placing a queen in each column, recurse, then remove and try next column.