用回溯法实现8皇后问题，输出所有可能的解

以下是使用Python实现的8皇后问题的回溯法解法：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def is_valid(board, row, col):
            # 检查列是否有冲突
            for i in range(row):
                if board[i][col] == 'Q':
                    return False
            # 检查左上方是否有冲突
            i, j = row - 1, col - 1
            while i >= 0 and j >= 0:
                if board[i][j] == 'Q':
                    return False
                i, j = i - 1, j - 1
            # 检查右上方是否有冲突
            i, j = row - 1, col + 1
            while i >= 0 and j < n:
                if board[i][j] == 'Q':
                    return False
                i, j = i - 1, j + 1
            return True
        
        def backtrack(board, row):
            if row == n:
                res.append(["".join(row) for row in board])
                return
            for col in range(n):
                if is_valid(board, row, col):
                    board[row][col] = 'Q'
                    backtrack(board, row + 1)
                    board[row][col] = '.'
        
        res = []
        board = [['.' for _ in range(n)] for _ in range(n)]
        backtrack(board, 0)
        return res

在这个解法中，我们使用了一个二维数组`board`来表示棋盘，其中每个元素可以是'Q'或'.'，分别表示皇后和空格。我们使用`is_valid(board, row, col)`函数来检查在(row, col)位置放置皇后是否合法，如果合法返回True，否则返回False。在回溯函数`backtrack(board, row)`中，我们从第0行开始遍历每一行，在每一行中，我们遍历每一列，如果在当前位置放置皇后合法，我们就将这个位置标记为'Q'，然后递归调用`backtrack(board, row + 1)`，当递归完成后，我们将这个位置重新标记为'.'，然后继续遍历下一列。如果在第n行放置皇后时，我们找到了一组解，我们将这个解添加到结果列表中。最后，我们返回结果列表。

这个解法的时间复杂度为O(N!)，其中N为棋盘大小。因为每一行必须放置一个皇后，所以一共有N种选择。在第一行放置皇后后，第二行不可能在同一列上放置皇后，所以有(N-1)种选择，以此类推。因此总共有N * (N-1) * ... * 1 = N!种可能的棋盘状态。