回溯經典問題#

一、N 皇后問題（LeetCode 51/52）#

在 N×N 棋盤上放置 N 個皇后，使它們互不攻擊。

攻擊範圍#

皇后可攻擊：橫向（行）、縱向（列）、斜向（撇）、反斜向（捺）

每一行只能有一個皇后，因此可以將「行」視為遞迴深度，只需決定每行皇后放在哪一列。

快速判斷合法性#

用三個集合記錄「被攻擊的區域」，判斷時間降為 O(1)：

集合	記錄內容	數學特性
cols	被佔用的列	col
pie (撇 `/`)	左下到右上斜線	row + col = 常數
na (捺 `\`)	左上到右下斜線	row - col = 常數

程式碼框架#

def solveNQueens(n):
    result = []

    def dfs(row, cols, pie, na, path):
        if row >= n:
            result.append(path)
            return

        for col in range(n):
            # 剪枝：檢查是否衝突
            if col in cols or (row + col) in pie or (row - col) in na:
                continue

            # 遞迴（傳入新的集合狀態）
            dfs(row + 1,
                cols | {col},
                pie | {row + col},
                na | {row - col},
                path + [col])

    dfs(0, set(), set(), set(), [])
    return result

若使用全域集合，必須在遞迴返回後手動移除剛加入的元素（回溯）。

複雜度#

時間：O(N!)
空間：O(N)

二、數獨問題（LeetCode 36/37）#

數獨規則#

在 9×9 格子填入 1-9，滿足：

每行 1-9 各出現一次
每列 1-9 各出現一次
每個 3×3 九宮格 1-9 各出現一次

LeetCode 36：驗證數獨#

檢查當前盤面是否合法（不需判斷有解）。

解法：走訪 9×9 盤面，用三組陣列/集合分別記錄行、列、九宮格的數字出現情況。

九宮格座標映射：格子 (i, j) 對應的九宮格索引為 (i/3, j/3)

LeetCode 37：解數獨#

填滿空格，找到一個解。

回溯解法：

找到第一個空格
嘗試填入 1-9
檢查合法性
合法則遞迴處理下一個空格
失敗則撤銷（回溯），嘗試下一個數字

程式碼實作

def solveSudoku(board):
    def isValid(row, col, num):
        # 檢查行
        if num in board[row]:
            return False
        # 檢查列
        if num in [board[i][col] for i in range(9)]:
            return False
        # 檢查九宮格
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == num:
                    return False
        return True

    def solve():
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in '123456789':
                        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，透過約束條件剪枝。