from typing import List
# 八皇后问题，用递归的方法来写。
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # 如果n < 1直接返回空列表
        if n < 1:return []
        # 定义变量用来存放最后的结果
        self.res = []
        # 定义几个集合，用来确保行和列，对角线只有一个皇后，
        # 这里我们以行来遍历，因此只需要定义列，两个对角线
        self.col,self.pie,self.na = set(),set(),set()
        self.dfs(n,0,[])
        return self.res
    def dfs(self,n,row,cur):
        # 递归完成，将结果放入self.res
        if row == n:
            # 注意这里的写法。
            # 不能写成self.res.append(cur)
            self.res.append(cur[:])
            return
        # 进行遍历列。
        for index in range(n):
            # 确保当前行，列，对角线没有皇后
            if index in self.col or index + row in self.pie or index - row in self.na :
                continue
            str1 = ""
            # 进行字符串的拼接
            for index1 in range(n):
                if index1 == index :
                    str1 += "Q"
                else :str1 += "."
            # cur为临时列表
            cur.append(str1)
            # 已经添加过字符串了，因此将当前行，列对角线的值写入集合
            self.col.add(index)
            self.pie.add(index + row)
            self.na.add(index - row)
            # 然后进行递归下一行
            self.dfs(n,row + 1,cur)
            # 注意递归完成后一定要清除当前行列，对角线的数据。
            cur.remove(str1)
            self.col.remove(index)
            self.pie.remove(index + row)
            self.na.remove(index - row)

A = Solution()
print(A.solveNQueens(8))
print(A.solveNQueens(4))