題目描述
52. N-Queens II 題目是經典的組合優化問題，它要求解出一個 n x n 的棋盤上，放置 n 個皇后，且要求皇后們不互相攻擊，並計算出所有合法的解的數量。
題目要求
- 輸入：一個整數
n，表示棋盤的大小（即n x n的棋盤）。 - 輸出：所有合法解的數量。
這題與 51. N-Queens 題目相似，唯一不同的是，這題只要求返回解的數量，而不是列出所有解。
範例
範例 1
輸入：n = 4
輸出：2
範例 2
輸入：n = 1
輸出：1
解題思路
這題其實是 51. N-Queens 題目的簡化版，只需要計算解的數量即可。因此，解法可以使用與 51. N-Queens 題目相同的回溯法（Backtracking），但我們這次不需要將每個合法解加入結果列表，只需要統計合法解的數量。
關鍵概念：
- 回溯法：我們將每一行看作一個選擇，逐行嘗試放置皇后，並檢查每次放置後是否會和其他皇后互相攻擊。如果成功放置
n個皇后，則解的數量加一。 - 優化回溯：用 位元運算 (Bitwise Operations) 來管理列與對角線的佔用狀態，大幅加速判斷。
解法一：回溯法
思路
- 使用回溯法，每次在新的一行放置皇后，並檢查該列、主對角線、次對角線是否可行。
- 如果
n個皇后都放置完成，計數器加一。 - 回溯時恢復狀態，繼續嘗試其他可能性。
程式碼
class Solution:
def totalNQueens(self, n: int) -> int:
def backtrack(row):
if row == n:
nonlocal count
count += 1
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1)
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
count = 0
cols = set()
diag1 = set()
diag2 = set()
backtrack(0)
return count
時間與空間複雜度
- 時間複雜度：O(n!)，每行最多可放 n 個皇后，但每次選擇都會減少可用選擇數，因此複雜度近似 O(n!)。
- 空間複雜度：O(n)，只使用了 cols、diag1 和 diag2 三個集合，額外空間需求為 O(n)。
解法二：位元運算優化回溯（Bitwise Operations）
思路
- 用 整數的二進位表示 來替代
set，減少記憶體佔用並加速查詢。 - 用
bitwise AND (&)快速檢查該列和對角線是否可行。
程式碼
class Solution:
def totalNQueens(self, n: int) -> int:
def backtrack(row, cols, diag1, diag2):
if row == n:
return 1
count = 0
available_positions = ((1 << n) - 1) & ~(cols | diag1 | diag2)
while available_positions:
position = available_positions & -available_positions # 取得最右邊的1
available_positions &= available_positions - 1 # 移除這個位置
count += backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)
return count
return backtrack(0, 0, 0, 0)
時間與空間複雜度
- 時間複雜度：O(n!)，與傳統回溯法相同，但位運算加速了狀態檢查，使得實際運行速度更快。
- 空間複雜度：O(n)，只需要遞迴堆疊，沒有使用 set，。
結論
52. N-Queens II 題目與 51. N-Queens 題目非常相似，主要的區別在於我們只需要返回解的數量，而不是列出所有的解。這題考察了回溯法的應用，以及如何利用剪枝技術提高效率。回溯法的核心是“嘗試”與“撤回”，這對於處理組合類問題十分有效。
這道題目讓我們再次認識到回溯法的強大，並且能夠進一步掌握如何在遞歸過程中進行優化。希望這篇文章能幫助你更好地理解這個問題，並能在其他類似問題中應用回溯法。
