class Solution:
    def solveNQueens(self, n):# 返回：List[List[str]], n:int
        # 生成一个棋盘 ,queens存放每一列的Q
        def generateBoard():
            board = list()
            for i in range(n):
                row[queens[i]] = "Q"   #  queens中记录了每一行中对应Q的列位置
                board.append("".join(row)) # 将每行情况添加至board
                row[queens[i]] = "."       #  还原row，继续下一行
            return board

        def backtrack(row: int):
            if row == n: # 遍历完行，递归结束
                board = generateBoard()  #此时生成带有Q的棋盘
                solutions.append(board)  # 将方案添加至solutions列表中
            else:
                for i in range(n):      
                     # 如果对当前行的每一列在三个存放后的集合中，则继续在列中找
                    if i in columns or row - i in diagonal1 or row + i in diagonal2:
                        continue
                    queens[row] = i  # 没在上述三个集合中，则添加Q       
                    columns.add(i)   # 在上述三个集合中，添加位置坐标
                    diagonal1.add(row - i)# 左上至右下斜线
                    diagonal2.add(row + i)# 左下至右上斜线 
                    backtrack(row + 1)    # 递归下一行
                    columns.remove(i)     # 回溯
                    diagonal1.remove(row - i)
                    diagonal2.remove(row + i)
                    
        solutions = list()
        queens = [-1] * n
        columns = set()
        diagonal1 = set()
        diagonal2 = set()
        row = ["."] * n
        backtrack(0)
        return solutions

a= Solution()
a.solveNQueens(4)