用python写N皇后的题解

N皇后问题是指在一个N*N的棋盘上放置N个皇后，使得每行每列和对角线上都只有一个皇后。这是一个经典的回溯算法问题，可以用Python来实现。

1. 定义一个函数solveNQueens(n)，其中n为棋盘的行数，返回类型是一个列表，每个元素是一个长度为n的列表，代表一个合法的棋盘状态。

2. 在函数中定义一个递归函数backtrack(board, row)，其中board是一个n*n的矩阵，代表当前棋盘状态，row代表当前要放置皇后的行数。

3. 在backtrack函数中，先判断当前行数是否等于n，如果等于，说明已经找到了一种合法的棋盘状态，将当前棋盘状态添加到结果列表中。

4. 如果当前行数小于n，则遍历当前行的每个位置，判断该位置是否可以放置皇后。如果可以放置，则将该位置置为1，继续递归backtrack(board, row+1)；如果不可以放置，则将该位置置为0，继续遍历下一个位置。

5. 判断一个位置是否可以放置皇后的方法是检查该位置所在的行、列、左上角、右上角是否已经有皇后了。可以用四个列表分别记录每行、每列、每个左上角到右下角的对角线、每个右上角到左下角的对角线是否有皇后，如果都没有，则可以放置皇后。

6. 最后返回结果列表即可。

代码如下：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        board = [[0] * n for _ in range(n)]
        cols = [False] * n
        diag1 = [False] * (2*n-1)
        diag2 = [False] * (2*n-1)
        self.backtrack(board, 0, cols, diag1, diag2, res)
        return res
    
    def backtrack(self, board, row, cols, diag1, diag2, res):
        n = len(board)
        if row == n:
            res.append(self.make_board(board))
            return
        for col in range(n):
            if cols[col] or diag1[row+col] or diag2[row-col+n-1]:
                continue
            board[row][col] = 1
            cols[col] = diag1[row+col] = diag2[row-col+n-1] = True
            self.backtrack(board, row+1, cols, diag1, diag2, res)
            board[row][col] = 0
            cols[col] = diag1[row+col] = diag2[row-col+n-1] = False
            
    def make_board(self, board):
        return [''.join(['Q' if x else '.' for x in row]) for row in board]

时间复杂度：$O(N!)$，其中N为棋盘的行数。因为第一行有N种选择，第二行有N-2种选择（不能和第一行在同一列或对角线），第三行有N-4种选择，以此类推，总共有N!种选择。因此时间复杂度为$O(N!)$。

空间复杂度：$O(N^2)$，其中N为棋盘的行数。需要用一个n*n的矩阵来保存棋盘状态，以及四个长度为2*n-1的列表来保存每行、每列、每个左上角到右下角的对角线、每个右上角到左下角的对角线是否有皇后。因此空间复杂度为$O(N^2)$。