回溯法教學：原理、程式碼與範例

回溯法解決什麼問題

有些問題要求列出所有符合規則的排列方式，或只要找出其中任何一種：放置 8 個皇后使彼此不會攻擊、填滿數獨格子、列出總和等於目標值的所有子集、找出把字串切成字典單字的所有方法。這類問題沒有巧妙的公式，只能靠搜尋。盲目嘗試每一種完整組合實在太慢，但大多數部分組合在做了幾個選擇之後就已經不合法了。

回溯法在每一個選擇之後都檢查規則。一旦部分解違反規則，它就立刻放棄搜尋樹上的整個分支，退回去嘗試下一個選項。

用白話說明原理

1. 如果目前的部分解已經完整，就記錄下來。
2. 否則，對每一個可能的下一步選擇：如果這個選擇是允許的，就做出它（選擇）。
3. 遞迴下去，繼續擴充這個解（探索）。
4. 撤銷這個選擇，讓下一個選項從相同的狀態開始（撤銷）。

搜尋空間是一棵樹：根是空的解，每一層增加一個選擇，葉節點是完整的候選解。回溯法就是在這棵樹上做深度優先搜尋，而剪枝就是切掉不可能包含解的子樹。

範例：4 皇后

在 4 × 4 的棋盤上放 4 個皇后，每列一個，使任兩個皇后不在同一欄或同一條對角線上。欄編號為 0 到 3。

繼續搜尋會找到唯一的另一個解 2, 0, 3, 1，它是第一個解的鏡像。

Python 實作

用集合記錄已使用的欄與對角線，讓每次安全檢查都是 O(1)。在其中一種對角線上 row - col 是常數，在另一種對角線上 row + col 是常數。

def solve_n_queens(n):
    solutions, cols = [], []
    used_cols, diag1, diag2 = set(), set(), set()

    def place(row):
        if row == n:
            solutions.append(cols.copy())   # copy, not the live list
            return
        for col in range(n):
            if col in used_cols or row - col in diag1 or row + col in diag2:
                continue                    # prune: square is attacked
            cols.append(col)                # choose
            used_cols.add(col); diag1.add(row - col); diag2.add(row + col)
            place(row + 1)                  # explore
            cols.pop()                      # unchoose
            used_cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

    place(0)
    return solutions

print(solve_n_queens(4))       # [[1, 3, 0, 2], [2, 0, 3, 1]]
print(len(solve_n_queens(8)))  # 92

同一個模板可以產生所有子集與所有排列：

def subsets(items):
    result, current = [], []

    def go(i):
        if i == len(items):
            result.append(current.copy())
            return
        current.append(items[i]); go(i + 1); current.pop()   # take items[i]
        go(i + 1)                                            # skip items[i]

    go(0)
    return result

def permutations(items):
    result, current, used = [], [], [False] * len(items)

    def go():
        if len(current) == len(items):
            result.append(current.copy())
            return
        for i, x in enumerate(items):
            if not used[i]:
                used[i] = True; current.append(x)
                go()
                used[i] = False; current.pop()

    go()
    return result

print(subsets([1, 2, 3]))
# [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

在實際程式碼中，若只需要一般的子集和排列，itertools.combinations 與 itertools.permutations 更快。需要用特定問題的規則來剪枝時，再自己寫回溯法。

時間與空間複雜度

回溯法不可能比輸出的大小更快：如果你必須列出 n! 個排列，至少需要 n! 步。剪枝只能藉由跳過不會產生任何結果的分支來幫忙。

變化版本與常見錯誤

• 忘了撤銷：如果遞迴呼叫之後沒有還原狀態，後面的分支就會看到過時的選擇。
• 加入的是仍在變動的串列：result.append(current) 儲存的是之後會被改動的參考；請改成 append current.copy()。
• 輸入中有重複元素：先排序，並在同一層跳過與前一個相等的元素，以避免產生重複的子集或排列。
• 找到第一個解就停止：當一個解就夠用時（如數獨求解器），讓遞迴回傳 True 並停止迴圈。
• 更好的排序：先嘗試限制最多的選擇（數獨中就是候選數字最少的空格）。這通常能大幅縮小搜尋樹。

何時使用與實際應用

• 限制滿足問題：數獨、填字遊戲、地圖著色、課表編排與考試排程。
• SAT 求解器與 Prolog 風格的邏輯引擎，都建立在帶有強力剪枝的回溯搜尋上。
• 許多語言的正規表達式引擎（包括 Python 的 re）都使用回溯；寫得不好的模式可能造成指數級的回溯（「災難性回溯」）。
• 面試題目：子集、排列、組合總和、N 皇后、網格中的單字搜尋、回文分割、括號生成、電話號碼的字母組合。