leetcode-51 N-Queens

[51] N-Queens

Key Concept: Backtracking with Constraint Validation - Place queens row by row. For each row, try each column and check if it's safe (no conflicts with previously placed queens). Backtrack if no valid position found.

Optimization: Use sets to track attacked columns, diagonals, and anti-diagonals for O(1) conflict checking.

# 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.
# Each solution contains a distinct board configuration where 'Q' and '.'
# 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

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

        # Track attacked positions for O(1) lookup
        cols = set()
        diagonals = set()       # row - col is constant on diagonal
        anti_diagonals = set()  # row + col is constant on anti-diagonal

        def backtrack(row):
            # Base case: placed all queens
            if row == n:
                result.append([''.join(row) for row in board])
                return

            # Try placing queen in each column of current row
            for col in range(n):
                # Check if position is under attack
                if (col in cols or
                    (row - col) in diagonals or
                    (row + col) in anti_diagonals):
                    continue

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

                # Recurse to next row
                backtrack(row + 1)

                # Backtrack: remove queen
                board[row][col] = '.'
                cols.remove(col)
                diagonals.remove(row - col)
                anti_diagonals.remove(row + col)

        backtrack(0)
        return result

# Time Complexity: O(n!) - n choices for first row, n-2 for second, etc.
# Space Complexity: O(n^2) - board storage
#
# Key Insights:
# 1. Process row by row (only one queen per row possible)
# 2. Track columns and diagonals with sets for O(1) checking
# 3. Diagonal: row - col is constant
# 4. Anti-diagonal: row + col is constant
#
# This is a classic backtracking problem with constraint satisfaction