python-leetcode 61.N皇后

题目：

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

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

---

每个皇后必须位于不同行和不同列，因此将 N 个皇后放置在 N×N 的棋盘上，一定是每一行有且仅有一个皇后，每一列有且仅有一个皇后，且任何两个皇后都不能在同一条斜线上。基于上述发现，可以通过回溯的方式寻找可能的解。

回溯的具体做法是：使用一个数组记录每行放置的皇后的列下标，依次在每一行放置一个皇后。每次新放置的皇后都不能和已经放置的皇后之间有攻击：即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上，并更新数组中的当前行的皇后列下标。当 N 个皇后都放置完毕，则找到一个可能的解。当找到一个可能的解之后，将数组转换成表示棋盘状态的列表，并将该棋盘状态的列表加入返回列表。

由于每个皇后必须位于不同列，因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有 N 列可以选择，第二个皇后最多有 N−1 列可以选择，第三个皇后最多有 N−2 列可以选择（如果考虑到不能在同一条斜线上，可能的选择数量更少），因此所有可能的情况不会超过 N! 种，遍历这些情况的时间复杂度是 O(N!)。

为了降低总时间复杂度，每次放置皇后时需要快速判断每个位置是否可以放置皇后，显然，最理想的情况是在 O(1) 的时间内判断该位置所在的列和两条斜线上是否已经有皇后。

方法一：基于集合的回溯

为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合 columns、diagonals 
1和 diagonals2分别记录每一列以及两个方向的每条斜线上是否有皇后。

列的表示法很直观，一共有 N 列，每一列的下标范围从 0 到 N−1，使用列的下标即可明确表示每一列。

如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。

方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0) 和 (3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。

方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 (3,0) 和 (1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。

每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。

class Solution(object):def solveNQueens(self, n):""":type n: int:rtype: List[List[str]]"""def generateBoard():  #生成棋盘board=[]  #用于存储棋盘的每一行for i in range(n):  #遍历所有行，按queens[i]记录的位置放至Qrow[queens[i]]="Q"  #row 是 [".", ".", ".", "."]（初始化的空白行）#queens[i]是皇后在当前行i的索引#在queens[i]位置放Q,queens[0] = 1（表示皇后在第 0 行的 第 1 列）#row = [".", "Q", ".", "."]board.append("".join(row))#将列表转换为字符串,作为棋盘格的一行row[queens[i]]="."  #恢复row为初始状态return board  #作为当前皇后排列的字符串表示def dfs(row):  #当前正在处理的行号（从 0 到 n-1）if row==n:  #所有行都放置完毕board=generateBoard() # 生成一个合法的棋盘solutions.append(board) #保存else:for i in range(n): #遍历当前行 row 的所有列 iif i in columns or row-i in diagonal1 or row+i in diagonal2:#皇后的列, 记录右下↘对角线 ,记录左下↙对角线continue #若 i 被占用，直接跳过该列queens[row]=i  #录当前行皇后放置的列号columns.add(i) #记录当前列被占用diagonal1.add(row-i)#记录对角线被占用diagonal2.add(row+i) #记录对角线被占用dfs(row+1)#递归尝试下一行的皇后摆放columns.remove(i)#回溯，撤销当前位置的皇后diagonal1.remove(row-i)#回溯，撤销对角线的占用状态diagonal2.remove(row+i)solutions=[] #存储所有合法的 N 皇后解法queens=[-1]*n #记录每一行皇后的位置，初始化-1表示未放置columns=set([])#记录被占用的列diagonal1=set([])diagonal2=set([])row=["."]*n         #用于构造棋盘，初始时所有行都是 "...." dfs(0)return solutions

时间复杂度：O(N!)其中 N 是皇后数量

空间复杂度：O(N)

---

方法二：基于位运算的回溯

方法一使用三个集合记录分别记录每一列以及两个方向的每条斜线上是否有皇后，每个集合最多包含 N 个元素，因此集合的空间复杂度是 O(N)。如果利用位运算记录皇后的信息，就可以将记录皇后信息的空间复杂度从 O(N) 降到 O(1)。

具体做法是，使用三个整数 columns、diagonals 1 和 diagonals 2分别记录每一列以及两个方向的每条斜线上是否有皇后，

每个整数有 N 个二进制位。棋盘的每一列对应每个整数的二进制表示中的一个数位，其中棋盘的最左列对应每个整数的最低二进制位，最右列对应每个整数的最高二进制位。用 0 代表可以放置皇后的位置，1 代表不能放置皇后的位置。

棋盘的边长和皇后的数量 N=8。如果棋盘的前两行分别在第 2 列和第 4 列放置了皇后（下标从 0 开始），则棋盘的前两行如下图所示。

如果要在下一行放置皇后，哪些位置不能放置呢？我们用 0 代表可以放置皇后的位置，1 代表不能放置皇后的位置。新放置的皇后不能和任何一个已经放置的皇后在同一列，因此不能放置在第 2 列和第 4 列，对应 columns=00010100(2)​。

新放置的皇后不能和任何一个已经放置的皇后在同一条方向一（从左上到右下方向）的斜线上，因此不能放置在第 4 列和第 5 列，对应 diagonals 1​ =00110000 (2)。其中，第 4 列为其前两行的第 2 列的皇后往右下移动两步的位置，第 5 列为其前一行的第 4 列的皇后往右下移动一步的位置。

新放置的皇后不能和任何一个已经放置的皇后在同一条方向二（从右上到左下方向）的斜线上，因此不能放置在第 0 列和第 3 列，对应 diagonals 2 =00001001。其中，第 0 列为其前两行的第 2 列的皇后往左下移动两步的位置，第 3 列为其前一行的第 4 列的皇后往左下移动一步的位置。

由此可以得到三个整数的计算方法：

• 初始时，三个整数的值都等于 0，表示没有放置任何皇后
• 在当前行放置皇后，如果皇后放置在第 i 列，则将三个整数的第 i 个二进制位（指从低到高的第 i 个二进制位）的值设为 1
• 进入下一行时，columns 的值保持不变，diagonals1​ 左移一位，diagonals2​ 右移一位，

  由于棋盘的最左列对应每个整数的最低二进制位，即每个整数的最右二进制位，因此对整数的移位操作方向和对棋盘的移位操作方向相反（对棋盘的移位操作方向是 diagonals 1 右移一位，diagonals 2​左移一位）。

• 

 每次放置皇后时，三个整数的按位或运算的结果即为不能放置皇后的位置，其余位置即为可以放置皇后的位置。

class Solution(object):def solveNQueens(self, n):""":type n: int:rtype: List[List[str]]"""def generateBoard():  # 生成当前解对应的棋盘布局board = []  # 创建一个空列表用于存储最终的棋盘解法for i in range(n):row[queens[i]] = "Q"board.append("".join(row))row[queens[i]] = "."return boarddef solve(row, columns, diagonals1, diagonals2):  # 当前正在放置皇后的行号, 已被占据的列，两条对角线if row == n:  # 递归终止条件，说明所有皇后已放置完毕board = generateBoard()  # 生成棋盘布局，并存入 solutionssolutions.append(board)else:# (1 << n) - 1 生成 n 位全 1，表示所有列都可用，并计算当前可选的列availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2))while availablePositions:  # 遍历所有可选的位置position = availablePositions & (-availablePositions)  # 取 availablePositions 的最低位 1，即当前可选的最左侧列availablePositions = availablePositions & (availablePositions - 1)  # 移除当前选择的位置，以便下次循环选择下一个位置column = bin(position - 1).count("1")  # 计算当前皇后应放置的列索引，统计 1 的个数，得到列索引queens[row] = column  # 记录 row 行的皇后放置在 column 列solve(row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1)  # 递归进入下一行，更新列和主副对角线solutions = []  # 存储所有可能的 N 皇后解法queens = [-1] * n  # 记录每行皇后的列索引，初始化为 -1 表示未放置row = ["."] * n  # 构造棋盘行，初始时所有单元格都是 "."solve(0, 0, 0, 0)  # 递归从第 0 行开始尝试放置皇后，初始时所有列和对角线都是可用的return solutions

时间复杂度：O(N!)

空间复杂度：O(N)

作者：力扣官方题解