N-Queens – Solution & Complexity

def solve_n_queens(n: int) -> list[list[str]]:
    cols = [False] * n
    diag = [False] * (2 * n - 1)
    anti = [False] * (2 * n - 1)
    queens = [-1] * n
    result = []

    def build_board() -> list[str]:
        board = []
        for row in range(n):
            chars = ['.'] * n
            chars[queens[row]] = 'Q'
            board.append(''.join(chars))
        return board

    def dfs(row: int) -> None:
        if row == n:
            result.append(build_board())
            return

        for col in range(n):
            d = row - col + n - 1
            a = row + col
            if cols[col] or diag[d] or anti[a]:
                continue

            cols[col] = diag[d] = anti[a] = True
            queens[row] = col
            dfs(row + 1)
            queens[row] = -1
            cols[col] = diag[d] = anti[a] = False

    dfs(0)
    return result