回溯經典問題#
N 皇后問題（N 皇后 ↗ / N 皇后 II ↗）#
在 N×N 棋盤上放置 N 個皇后，使它們互不攻擊。
攻擊範圍#
皇后可攻擊：橫向（行）、縱向（列）、斜向（撇）、反斜向（捺）
每一行只能有一個皇后，因此可以將「行」視為遞迴深度，只需決定每行皇后放在哪一列。
快速判斷合法性#
用三個集合記錄「被攻擊的區域」，判斷時間降為 O(1)：
| 集合 | 記錄內容 | 數學特性 |
|---|---|---|
| cols | 被佔用的列 | col |
pie (撇 /) | 左下到右上斜線 | row + col = 常數 |
na (捺 \) | 左上到右下斜線 | row - col = 常數 |
程式碼框架#
fun solveNQueens(n: Int): List<List<Int>> {
val result = mutableListOf<List<Int>>()
fun dfs(row: Int, cols: Set<Int>, pie: Set<Int>, na: Set<Int>, path: List<Int>) {
if (row >= n) {
result.add(path)
return
}
for (col in 0 until n) {
// 剪枝：檢查是否衝突
if (col in cols || (row + col) in pie || (row - col) in na) continue
// 遞迴（傳入新的集合狀態，用 + 產生新集合、自動「回溯」）
dfs(
row + 1,
cols + col,
pie + (row + col),
na + (row - col),
path + col,
)
}
}
dfs(0, emptySet(), emptySet(), emptySet(), emptyList())
return result
}若使用全域集合，必須在遞迴返回後手動移除剛加入的元素（回溯）。
複雜度#
- 時間：
O(N!) - 空間：
O(N)
數獨問題（有效的數獨 ↗ / 解數獨 ↗）#
數獨規則#
在 9×9 格子填入 1-9，滿足：
- 每行 1-9 各出現一次
- 每列 1-9 各出現一次
- 每個 3×3 九宮格 1-9 各出現一次
驗證數獨 ↗#
檢查當前盤面是否合法（不需判斷有解）。
解法：走訪 9×9 盤面，用三組陣列/集合分別記錄行、列、九宮格的數字出現情況。
九宮格座標映射：格子 (i, j) 對應的九宮格索引為
(i/3, j/3)
解數獨 ↗#
填滿空格，找到一個解。
回溯解法：
- 找到第一個空格
- 嘗試填入 1-9
- 檢查合法性
- 合法則遞迴處理下一個空格
- 失敗則撤銷（回溯），嘗試下一個數字
程式碼實作
fun solveSudoku(board: Array<CharArray>) {
fun isValid(row: Int, col: Int, num: Char): Boolean {
for (i in 0 until 9) {
// 檢查行與列
if (board[row][i] == num) return false
if (board[i][col] == num) return false
}
// 檢查九宮格
val boxRow = 3 * (row / 3)
val boxCol = 3 * (col / 3)
for (i in boxRow until boxRow + 3) {
for (j in boxCol until boxCol + 3) {
if (board[i][j] == num) return false
}
}
return true
}
fun solve(): Boolean {
for (i in 0 until 9) {
for (j in 0 until 9) {
if (board[i][j] == '.') {
for (num in '1'..'9') {
if (isValid(i, j, num)) {
board[i][j] = num
if (solve()) return true
board[i][j] = '.' // 回溯
}
}
return false // 1-9 都不行，回溯
}
}
}
return true // 填滿了
}
solve()
}最佳化策略#
| 最佳化方法 | 說明 |
|---|---|
| MRV（最少候選值優先） | 優先填「可選數字最少」的格子 |
| 預處理 | 先計算每個空格的候選數字 |
| 位運算 | 用 bitmask 表示數字佔用情況 |
遞迴函式必須有明確的終止條件。當走訪完整個棋盤且沒有返回 false 時，代表找到解，應立即 return true 終止所有遞迴。
問題對比#
| 問題 | 搜尋維度 | 每步選擇數 | 剪枝重點 |
|---|---|---|---|
| N 皇后 | 逐行放置 | N 列 | 行列斜線衝突 |
| 數獨 | 逐格填寫 | 9 個數字 | 行列九宮格衝突 |
| 括號生成 | 逐字元選擇 | 2 種括號 | 括號數量約束 |
這些問題的共同點：都是在解空間樹上進行 DFS，透過約束條件剪枝。