N-QueensN 皇后
逐列放置，用集合記錄被攻擊的欄與對角線。
用在：約束滿足問題的原型：排課、排班
01為什麼需要它
每門課要選一個時段和教室，同一位老師不能同時上兩門課、同一間教室不能同時有兩班、某些課不能排在同一天。一百多門課，手排要花幾個星期。
為什麼用它一次處理一門課，從可用的時段裡挑一個不衝突的，往下排下一門；全部時段都衝突就退回上一門課換一個時段。N 皇后是這種「約束滿足問題」最小的教科書版本：每一列放一個皇后，不能和已放的同欄、同對角線。
護理站每天要排三班，每個人有不能值的日子、連續值班的上限、和某些人不能同班的限制。要找出一份滿足所有規則的班表。
為什麼用它逐格填、每填一格就檢查所有規則、違反就回頭改上一格，這正是回溯。關鍵在「檢查衝突要快」：N 皇后用三個集合把每次檢查壓到 O(1)，排班則用同樣的思路預先建立每個人、每一天的佔用表。
手機上的數獨 app 要能驗證任何一盤有解，還要能給提示。人腦解法是「填一格、看看有沒有矛盾、有就擦掉重填」。
為什麼用它程式解法和人腦一模一樣：逐格嘗試 1 到 9，用列、欄、宮三組集合檢查衝突，走不通就回溯。數獨是 N 皇后的直接延伸，差別只在約束的形狀。
看到這些關鍵字就想到它：不能衝突、每列每欄只能一個、排課排班、約束滿足、放置後要檢查、走不通就換上一步、數獨。
02核心概念
N 皇后要在 n×n 的棋盤放 n 個皇后，任兩個不能在同一列、同一欄或同一對角線。第一個洞見是一列恰好一個：既然不能同列而且要放 n 個，每列必定剛好一個，所以只要決定「第 r 列的皇后放在哪一欄」。搜尋空間從「任選 n 格」變成「每列選一欄」，一下子小很多。
第二個洞見是衝突檢查要 O(1)。同欄的格子 c 相同；同一條「\」對角線的格子 r−c 相同；同一條「/」對角線的格子 r+c 相同。用三個集合記錄已放皇后的 c、r−c、r+c，判斷一格能不能放只要查三次。放皇后時把三個值加進去，撤銷時三個都要移除，漏掉一個之後的分支就會誤判。
搜尋本身就是回溯的三步：對第 r 列的每一欄 c，被攻擊就跳過（剪枝），否則做選擇、遞迴到 r+1、撤銷。若第 r+1 列每一欄都被攻擊，遞迴會直接返回，這就是「回溯」的時刻：拿掉第 r 列的皇后，換下一欄。整個過程是一棵深度 n 的樹上的 DFS，每個節點的分支數是那一列還沒被攻擊的欄數。
複雜度是指數的，粗略上界 O(n!)，剪枝後實際小得多；8 皇后有 92 組解，搜尋節點約兩千個。只數解不列出棋盤時，可以用位元遮罩取代集合：三個整數的第 c 位表示欄 c 是否被攻擊，換到下一列時「\」對角線整體左移一位、「/」對角線右移一位。這是 N 皇后最快的寫法，也是「用整數當集合」這個技巧的經典範例。
03演算法步驟
- 1準備
queens（每列的欄）和三個集合cols、diag1（r−c）、diag2（r+c）。dfs(r)表示「正在放第 r 列」。 - 2終止條件：
r == n，n 列都放好了，把queens轉成棋盤收進答案。 - 3對每個欄 c：若
c in cols或r-c in diag1或r+c in diag2，被攻擊，跳過。 - 4做選擇：
queens.append(c)，三個集合各加一個值，遞迴dfs(r + 1)。 - 5撤銷選擇：
queens.pop()，三個集合各移除一個值。這一列所有欄試完仍無解，就自然返回到上一列，也就是回溯。
04互動示範
4 皇后。一列一列放，淺黃格是被現有皇后攻擊的位置，每次試到被攻擊的格子會標出原因。當某一列每一欄都被攻擊，就拿掉上一列的皇后換下一欄，直到找到第一組解。
黃色底是被現有皇后攻擊的格子，深黃是這一步試到的被攻擊格。灰底是目前要放的那一列。每次判斷只查三個集合，O(1)。
05程式碼
列出所有解的集合版本，以及只數解數量的位元遮罩版本。
# N 皇后（LeetCode 51）：逐列放置，三個集合記錄被攻擊的欄與對角線
def solve_n_queens(n):
ans = []
queens = [] # queens[r] = 第 r 列皇后所在的欄
cols = set() # 被佔用的欄
diag1 = set() # r - c 相同的格子在同一條「\」對角線
diag2 = set() # r + c 相同的格子在同一條「/」對角線
def dfs(r):
if r == n: # 每一列都放好了
ans.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])
return
for c in range(n):
if c in cols or (r - c) in diag1 or (r + c) in diag2:
continue # 被攻擊，剪掉
queens.append(c) # 做選擇
cols.add(c); diag1.add(r - c); diag2.add(r + c)
dfs(r + 1)
queens.pop() # 撤銷選擇：三個集合都要復原
cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)
dfs(0)
return ans
# 只數解的數量（LeetCode 52）：用位元遮罩代替集合
# cols / d1 / d2 是 n 位元的整數，第 c 位為 1 代表這一列的欄 c 被攻擊
def total_n_queens(n):
full = (1 << n) - 1
def dfs(cols, d1, d2):
if cols == full: # n 個欄都放了皇后
return 1
count = 0
free = full & ~(cols | d1 | d2) # 這一列還能放的位置
while free:
bit = free & -free # 取最低的 1
free ^= bit
# 下一列：\ 對角線往右一欄（<< 1），/ 對角線往左一欄（>> 1）
count += dfs(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1)
return count
return dfs(0, 0, 0)
if __name__ == "__main__":
for row in solve_n_queens(4)[0]:
print(row) # .Q.. / ...Q / Q... / ..Q.
print(total_n_queens(8)) # 9206練習題
- LeetCode 36Valid Sudoku（先練衝突檢查）Medium
- LeetCode 473Matchsticks to Square（每根火柴放進四條邊之一，排序後剪枝）Medium
- LeetCode 51N-QueensHard
- LeetCode 52N-Queens II（位元遮罩）Hard
- LeetCode 37Sudoku Solver（列、欄、宮三組集合）Hard
- LeetCode 1655Distribute Repeating Integers（約束滿足加剪枝）Hard