from typing import List
# 八皇后问题	，用递归的方法来写	。
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # 假如n < 1立即回到空目录
        if n < 1:return []
        # 界定自变量用于储放最终的結果
        self.res = []
        # 界定好多个结合，用于保证 列和行，直线只有一个王后，
        # 这儿大家以行业解析xml	，因而只必须界定列，2个直线
        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
        # 开展解析xml列。
        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))
文章来源于网络，如有侵权请联系站长QQ61910465删除
本文版权归趣KUAI排www.SEOguruBlog.com 所有,如有转发请注明来出,竞价开户托管,seo优化请联系QQ→61910465