N 皇后問題：在 n x n 的棋盤上放置 n 個皇后，使得任意兩個皇后都不能互相攻擊（不在同一行、同一列、同一對角線）。回傳所有不同的解法。
Example:
Input: n = 4 Output: [[”.Q..”,”…Q”,“Q…”,”..Q.”],[”..Q.”,“Q…”,”…Q”,”.Q..”]]
Intuition
TIP
核心思路：逐行放置皇后，用集合記錄已佔用的列和對角線，回溯搜尋所有合法配置。
- 每一行恰好放一個皇后（保證不同行）
- 需要檢查：不同列、不同主對角線（row - col 相同）、不同副對角線（row + col 相同）
- 用三個 Set 分別追蹤已佔用的列、主對角線、副對角線
Approaches
1. Backtracking + Per-Cell Check — O(n!) / O(n^2)
- Idea: 逐行放皇后，每次放置後檢查是否與之前所有皇后衝突
- Time:
O(n!)- 第一行 n 種、第二行最多 n-1 種 … - Space:
O(n^2)- 棋盤
class Solution {
fun solveNQueens(n: Int): List<List<String>> {
val result = mutableListOf<List<String>>()
val board = Array(n) { CharArray(n) { '.' } }
fun isValid(row: Int, col: Int): Boolean {
for (r in 0 until row) {
if (board[r][col] == 'Q') return false
if (col - (row - r) >= 0 && board[r][col - (row - r)] == 'Q') return false
if (col + (row - r) < n && board[r][col + (row - r)] == 'Q') return false
}
return true
}
fun backtrack(row: Int) {
if (row == n) {
result.add(board.map { String(it) })
return
}
for (col in 0 until n) {
if (isValid(row, col)) {
board[row][col] = 'Q'
backtrack(row + 1)
board[row][col] = '.'
}
}
}
backtrack(0)
return result
}
}⭐ 2. Backtracking + Set Tracking (O(1) conflict) — O(n!) / O(n)
- Idea: 用三個 HashSet 分別追蹤已佔用的列（col）、主對角線（row - col）、副對角線（row + col），O(1) 判斷衝突
- Time:
O(n!) - Space:
O(n)- 三個 Set 各最多 n 個元素
class Solution {
fun solveNQueens(n: Int): List<List<String>> {
val result = mutableListOf<List<String>>()
val board = Array(n) { CharArray(n) { '.' } }
val cols = HashSet<Int>()
val diag1 = HashSet<Int>() // row - col (主對角線)
val diag2 = HashSet<Int>() // row + col (副對角線)
fun backtrack(row: Int) {
if (row == n) {
result.add(board.map { String(it) })
return
}
for (col in 0 until n) {
if (col in cols || (row - col) in diag1 || (row + col) in diag2) continue
board[row][col] = 'Q'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1)
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
}
}
backtrack(0)
return result
}
}Note: Math behind Diagonal Check
在 n x n 棋盤上：
- 同一列: col 值相同
- 主對角線（左上到右下）:
row - col值相同，因為沿對角線走一步 row+1, col+1，差值不變 - 副對角線（右上到左下）:
row + col值相同，因為沿對角線走一步 row+1, col-1，和值不變
所以只需要三個 Set 就能 O(1) 判斷任意位置是否安全。
🔑 Takeaways
- Pattern: 約束滿足問題（CSP）用回溯法搜尋，配合高效的衝突檢查來剪枝
- Key trick: 用
row - col和row + col表示兩條對角線，是棋盤問題中的經典技巧；Set 追蹤將衝突判斷從 O(n) 降到 O(1)