N-Queens Interview Question for Meta

# N-Queens Problem

The N-Queens problem is a classic puzzle where the goal is to place N chess queens on an N×N chessboard so that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal.

## Naive Approach (Brute Force)

A brute-force approach would involve trying all possible placements of queens on the board and checking if any two queens attack each other.  This is extremely inefficient.

## Optimal Approach (Backtracking)

A more efficient approach is to use backtracking. We can place queens one by one in each row. While placing a queen in a row, we check if it is safe to place it in the current column. If it is safe, we mark the column as occupied and move to the next row. If we reach the last row, we have found a solution. If we find that it is not safe to place a queen in any column in the current row, we backtrack and try a different column in the previous row.

```python
class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        def is_safe(board, row, col):
            # Check same column
            for i in range(row):
                if board[i][col] == 'Q':
                    return False
            
            # Check upper left diagonal
            for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
                if board[i][j] == 'Q':
                    return False
            
            # Check upper right diagonal
            for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
                if board[i][j] == 'Q':
                    return False
            
            return True

        def solve_n_queens_util(board, row):
            if row == n:
                solutions.append([''.join(row) for row in board])
                return
            
            for col in range(n):
                if is_safe(board, row, col):
                    board[row][col] = 'Q'
                    solve_n_queens_util(board, row + 1)
                    board[row][col] = '.'  # Backtrack

        solutions = []
        board = [['.' for _ in range(n)] for _ in range(n)]
        solve_n_queens_util(board, 0)
        return solutions

Explanation:

is_safe(board, row, col): This function checks if it is safe to place a queen at board[row][col]. It checks for queens in the same column and both diagonals.
solve_n_queens_util(board, row): This recursive function tries to place a queen in each column of the current row. If it's safe, it places the queen and recursively calls itself for the next row. If a solution is found (i.e., row == n), it's added to the solutions list. Backtracking is achieved by resetting the cell to '.' after the recursive call returns.

Example:

For n = 4, the code will produce the following solutions:

[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]

Big(O) Run-time Analysis

The time complexity of the backtracking algorithm for the N-Queens problem is O(N!), where N is the number of queens and the size of the board. This is because, in the worst case, the algorithm explores all possible permutations of queen placements. The is_safe function takes O(N) time in the worst case. This is a very rough upper bound, as backtracking prunes large portions of the search space.

Big(O) Space Usage Analysis

The space complexity is O(N^2) due to the storage of the board configuration. The recursion depth can be at most N, contributing O(N) to the space complexity. Therefore, the total space complexity is O(N^2).

Edge Cases

n = 1: The board is 1x1, and the solution is just one queen in that cell.
n = 2 or n = 3: There are no solutions because the queens will always attack each other.
n > 3: Solutions exist and are found by the backtracking algorithm.