本文共 1456 字，大约阅读时间需要 4 分钟。

LeetCode.jpg

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

image

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 *n *皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4

输出: [

["..Q.", // 解法 2

解释: 4 皇后问题存在两个不同的解法。

Python3实现

DFS 深度优先

51. N-Queens.PNG

# @author:leacoder # @des:  DFS 深度优先  N皇后class Solution:    def solveNQueens(self, n: int) -> List[List[str]]:        if n < 1 : return []  #        self.result = []        shu = [] # 竖方向是否被攻击        pie = [] # 撇方向是否被攻击  x y 坐标之和固定 x + y        na = []  # 捺方向是否被攻击  x y 坐标之差固定 x - y                self.DFS(n,shu,pie,na)                return self.generate(n)        def DFS(self,n,shu,pie,na): #深度优先搜索         p = len(shu) #  从 1 -> n        if p == n :            self.result.append(shu) #每层有且只能放一个            return None        for q in range(n): # 看成 x  每层枚举可能的 x            if q not in shu and p - q not in na and p + q not in pie: #这一层存在可能位置，向下层搜索                self.DFS(n,shu+[q],pie+[p+q],na+[p-q])  #深度优先搜索  将被攻击的 坐标记录下来             def generate(self,n):        board=[]        for res in self.result: #            for count in res:                board.append( "." * count + "Q" + "." * (n - count -1))  #将所有存放在一个列表中        finalresult = []        for i in range(0,len(board),n):  # 按每n组成一个新列表，最后生成所需形式            finalresult.append(list(board[i:i+n]))        return finalresult

GitHub链接：

知乎个人首页：

个人Blog:

欢迎大家来一起交流学习

转载地址：https://blog.csdn.net/leacock1991/article/details/101490284 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！