回溯演算法：撤銷的勇氣

演算法背後的故事：迷宮

想像妳置身於一個巨大的石頭迷宮中。妳想找到出口。

• 妳來到一個岔路口：左還是右？妳選擇了左邊。
• 妳走了 10 分鐘，撞上了一堵死牆。
• 妳會坐在那裡哭嗎？不。妳會退回到上一個岔路口，嘗試右邊的路徑。

這就是 回溯演算法 (Backtracking)。它是一種系統地嘗試所有候選解的方法。如果一個候選解不可能導致有效的最終解，演算法就會「回溯」（撤銷最後一步），並嘗試下一個候選解。

本質上，它是在一棵「決策樹」上進行的 深度優先搜尋 (DFS)。

為什麼需要它？

• 智力遊戲： 解決數獨、填字遊戲或魔方。
• 最優化問題： N 皇后問題——在棋盤上放置 8 個皇后，使她們互不攻擊。
• 組合數學： 生成長度為 8 的所有可能密碼。
• 資源管理： 在複雜的約束條件下為工人分配任務。

演算法是如何「思考」的

該演算法遵循一個簡單的遞迴模板：

1. 狀態： 當前的解看起來是什麼樣的？
2. 選擇： 下一步有哪些可能的動作？
3. 約束檢查： 這個動作合法嗎？
4. 目標： 我們完成了嗎？
5. 撤銷 (The Undo)： 如果我們撞了牆，撤銷上一步的選擇，嘗試下一個。

剪枝 (Pruning)： 一個聰明的冒險者如果在路口看到了「死路」的牌子，就不會再往裡走 10 分鐘。在回溯中，剪枝是指因為違反規則而儘早砍掉整個決策分支的行為。

工程決策：狀態空間爆炸

回溯演算法可能非常慢，因為可能性的數量呈指數級增長（$O(2^N)$ 或 $O(N!)$）。

• 優化： 工程師使用「啟發式搜尋」來優先嘗試最可能的路徑。
• 儘早失敗： 妳越早檢測到死胡同，演算法執行得就越快。

實作參考 (Python)

# N 皇后問題：在 NxN 的棋盤上放置 N 個皇后
def solve_n_queens(n):
    result = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    
    def is_safe(row, col):
        # 檢查列
        for i in range(row):
            if board[i][col] == 'Q': return False
        # 檢查左上對角線
        for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
            if board[i][j] == 'Q': return False
        # 檢查右上對角線
        for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
            if board[i][j] == 'Q': return False
        return True

    def backtrack(row):
        # 基礎情況：達成目標
        if row == n:
            result.append(["".join(r) for r in board])
            return

        # 嘗試所有選擇（每一列）
        for col in range(n):
            if is_safe(row, col):
                # 1. 做出選擇
                board[row][col] = 'Q'
                # 2. 探索
                backtrack(row + 1)
                # 3. 撤銷選擇 (回溯)
                board[row][col] = '.'

    backtrack(0)
    return result

# 使用範例
solutions = solve_n_queens(4)
print(f"4 皇后問題的解法總數: {len(solutions)}")

小結

回溯演算法教會我們：探索需要謙遜。我們必須願意承認自己是錯的，並有紀律地回到上一個確定的點。它提醒我們，在充滿無限可能的世界裡，尋找真理的唯一方法就是嘗試一切——並知道何時停止。