題目：

按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。

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)

作者：力扣官方題解
?

?