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

Additional information

• 1 <= n <= 9

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 as shown above.

Example 2:

Input: n = 1

Output: [["Q"]]

Brute Force Backtracking (Naive Validation)

Intuition

To place queens without them attacking each other, we know one simple rule right away: we can only place exactly one queen per row.

Therefore, we can use a Depth-First Search (DFS) backtracking approach that proceeds row by row. At each row, we try placing a queen in every single column. To ensure the placement is valid, we naively check all previously placed queens to see if they share the same column, or share the same diagonal. If a spot is safe, we place the queen, move to the next row, and eventually backtrack if we hit a dead end.

Algorithm

1. Initialize a list of lists board filled with "." representing the NxN empty board.
2. Initialize an empty list res to hold the final valid board states.
3. Create a helper function is_safe(row, col) that loops through all previous rows:

• Check if there's a queen in the exact same column col.
• Check if there's a queen in the top-left diagonal.
• Check if there's a queen in the top-right diagonal.

4. Create a recursive dfs(r) function where r is the current row.
5. Base Case: If r == n, we successfully placed all n queens! Join the rows into strings and append the formatted board to res.
6. Loop & Recurse: Loop through every column c from 0 to n - 1.

• If is_safe(r, c) returns True, place a queen: board[r][c] = "Q".
• Recursively call dfs(r + 1).
• Backtrack by removing the queen: board[r][c] = ".".

7. Call dfs(0) and return res.

def solve_n_queens(n: int) -> list[list[str]]:
    board = [["."] * n for _ in range(n)]
    res = []
    
    def is_safe(r, c):
        # Check current column above
        for i in range(r):
            if board[i][c] == "Q":
                return False
                
        # Check top-left diagonal
        i, j = r - 1, c - 1
        while i >= 0 and j >= 0:
            if board[i][j] == "Q":
                return False
            i -= 1
            j -= 1
            
        # Check top-right diagonal
        i, j = r - 1, c + 1
        while i >= 0 and j < n:
            if board[i][j] == "Q":
                return False
            i -= 1
            j += 1
            
        return True

    def dfs(r):
        if r == n:
            res.append(["".join(row) for row in board])
            return
            
        for c in range(n):
            if is_safe(r, c):
                board[r][c] = "Q"
                dfs(r + 1)
                board[r][c] = "."
                
    dfs(0)
    return res

Time & Space Complexity

• Time complexity: O(N! * N)

• Reason: Finding valid permutations on a board inherently behaves like a factorial N! scaling. In this naive approach, every time we attempt to place a queen, we also spend O(N) time scanning the board backwards to validate it, resulting in heavy overhead.

• Space complexity: O(N^2)

• Reason: The board array requires O(N^2) space to hold all the characters, and the recursion stack reaches a maximum depth of N.

Optimal Backtracking with Sets

Intuition

We can completely eliminate the expensive O(N) scanning loop by using Hash Sets to remember the "attack zones" of the queens we've already placed.

Whenever we place a queen at (r, c), we know she attacks:

1. The entire column c.
2. The entire positive diagonal. If you observe grid coordinates, every square on the same top-right to bottom-left diagonal shares the exact same row + col sum!
3. The entire negative diagonal. Every square on the same top-left to bottom-right diagonal shares the exact same row - col difference!

By maintaining three sets (cols, pos_diag, neg_diag), checking if a cell is safe instantly becomes an O(1) operation.

Algorithm

1. Initialize cols, pos_diag, and neg_diag as empty sets.
2. Initialize the empty board and res list.
3. Define dfs(r) for the current row.
4. Base Case: If r == n, format the board and append to res.
5. Loop & Prune: Iterate over column c from 0 to n - 1.

• If c in cols, or (r + c) in pos_diag, or (r - c) in neg_diag, skip this column (continue).
• Mark the attack zones: add c, (r + c), and (r - c) to their respective sets.
• Place the queen: board[r][c] = "Q".
• Recurse: dfs(r + 1).
• Backtrack: Remove the attack zones from the sets, and remove the queen from the board: board[r][c] = ".".

6. Call dfs(0) and return res.

def solve_n_queens(n: int) -> list[list[str]]:
    cols = set()
    pos_diag = set() # r + c
    neg_diag = set() # r - c
    
    res = []
    board = [["."] * n for _ in range(n)]
    
    def dfs(r):
        if r == n:
            res.append(["".join(row) for row in board])
            return
            
        for c in range(n):
            if c in cols or (r + c) in pos_diag or (r - c) in neg_diag:
                continue
                
            # Place Queen
            cols.add(c)
            pos_diag.add(r + c)
            neg_diag.add(r - c)
            board[r][c] = "Q"
            
            dfs(r + 1)
            
            # Backtrack
            cols.remove(c)
            pos_diag.remove(r + c)
            neg_diag.remove(r - c)
            board[r][c] = "."
            
    dfs(0)
    return res

Time & Space Complexity

• Time complexity: O(N!)

• Reason: The algorithm explores every valid permutation of queen placements. However, checking if a placement is valid is now an O(1) constant time operation thanks to the Hash Sets. This heavily prunes the decision tree and provides the optimal runtime.

• Space complexity: O(N^2)

• Reason: The board structure inherently requires O(N^2) space to store the NxN grid. The Hash Sets and the recursion stack require an additional O(N) space.