N 皇后問題：在 n x n 的棋盤上放置 n 個皇后，使得任意兩個皇后不能互相攻擊（不同行、不同列、不同對角線）。回傳解的數量。
Example:
Input: n = 4 Output: 2
Intuition
TIP
核心思路：與 51. N-Queens 相同的回溯，但只計數不需要記錄棋盤。
- 每行放一個皇后，用回溯嘗試每列
- 用三個 Set（或 bitmask）追蹤被攻擊的列、主對角線、副對角線
- 因為只需計數，不需要建構棋盤，程式碼更簡潔
Approaches
1. Backtracking + HashSet — O(n!) / O(n)
- Idea: 逐行放置皇后，用 HashSet 記錄被佔用的列和對角線
- Time:
O(n!)- 每行的可選列逐步減少 - Space:
O(n)
class Solution {
fun totalNQueens(n: Int): Int {
val cols = mutableSetOf<Int>()
val diag1 = mutableSetOf<Int>() // row - col
val diag2 = mutableSetOf<Int>() // row + col
var count = 0
fun backtrack(row: Int) {
if (row == n) {
count++
return
}
for (col in 0 until n) {
if (col in cols || (row - col) in diag1 || (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)
}
}
backtrack(0)
return count
}
}⭐ 2. Backtracking + Bitmask — O(n!) / O(n)
- Idea: 用三個整數的位元表示佔用狀態，位元運算比 HashSet 更快
- Time:
O(n!) - Space:
O(n)- 遞迴深度
class Solution {
fun totalNQueens(n: Int): Int {
var count = 0
fun backtrack(row: Int, cols: Int, diag1: Int, diag2: Int) {
if (row == n) {
count++
return
}
// 可用位置 = 所有位置 - 被攻擊的位置
var available = ((1 shl n) - 1) and (cols or diag1 or diag2).inv()
while (available != 0) {
// 取最低位的 1（lowbit trick）
val pos = available and (-available)
available = available xor pos
backtrack(
row + 1,
cols or pos,
(diag1 or pos) shl 1,
(diag2 or pos) shr 1
)
}
}
backtrack(0, 0, 0, 0)
return count
}
}🔑 Takeaways
- Pattern: N 皇后 → 逐行回溯 + 列 / 對角線衝突檢測
- Key trick: Bitmask 方式用
lowbit = x & (-x)逐一枚舉可用位置；主對角線往左移、副對角線往右移來傳遞攻擊範圍；與 51. N-Queens 的差異僅在於只計數不需記錄解