從整個造出候選，到一次只下一個選擇
前面幾篇指南留給我們一張令人不安的帳單。生成與測試既正確又極其簡單，但它每次都把候選完整造好才檢查，而它必須走遍的搜尋空間大得驚人——2^n 個子集、n! 種排列。浪費的不只是規模，更是時機。要擺八個皇后，生成與測試法會樂呵呵地造出一整盤棋，其中第 1、第 2 個皇后早已互相攻擊，然後還把第 3 到第 8 個皇后以一切可能的方式填滿，最後才檢測並否決掉這全部。數以百萬計的完整棋盤，為了第二步之後就看得見的衝突而陪葬。
解法是換一種姿態。不要先造出完成的候選再去評判，而是逐步地建構候選——一次只下一個決定——並在每個部分候選成長的當下就評判它。一個部分候選就是這些選擇的一個前綴：「第 1 個皇后放在第 3 行，第 2 個放在第 6 行，其餘還沒決定。」如果連這個前綴都已經違反規則，那麼它的任何補完都不可能有效，所以根本沒必要補完。我們把整個前綴丟掉，為最近的那個位置改試別的選擇。這個單一的想法——延伸、檢查、撤退——就是回溯法。
狀態空間樹，以及為何深度優先搜尋是自然的走法
把所有前綴排成一棵樹來想像。根是空候選，什麼都還沒決定。每個節點是一個部分候選，它的子節點是做出下一個決定的各種方式：從「第 1 個皇后已放好」出發，子節點就是第 2 個皇后各行位置的選擇。底部的葉子是完整候選。這就是狀態空間樹，它讓搜尋的結構變得鮮明——從根到某節點的一條路徑，恰好就是建構出那個部分候選的選擇序列。
那麼，我們該怎麼走這棵樹？深度優先。沿著一條分支一路俯衝，盡可能往深處下選擇；一旦撞上死路或葉子，就退回到最近一個還有未試子節點的節點，再次潛入。這正是在狀態空間樹上的以深度優先搜尋進行的回溯。那次撤退就是回溯裡的「回」：你把上一個選擇撤銷，把部分候選還原成上一層的樣子——確確實實地把剛放下的皇后擦掉，再試下一行。深度優先在這裡是對的紀律，因為它在記憶體中一次只保留一條根到節點的路徑，所以工作狀態很小：是 O(深度)，而非 O(節點數)。
solve(partial):
if partial is complete: report it; return
for each choice c that extends partial:
if feasible(partial + c): # the prune
solve(partial + c) # go deeper
# else: skip c's whole subtree
# falling off the loop = backtrack to caller剪枝：所有節省的來源
把一場暴力的樹遍歷變快的那一行，就是可行性檢查。在遞迴進入一個子節點之前，先問：這個部分候選還能被補完成一個有效候選嗎？如果答案可被證明為「不能」，我們就絕不進入那個子節點——而這單一個拒絕，便刪掉了它底下整棵子樹，連同它本會抵達的每一片葉子。這就是可行性剪枝，它就是整場遊戲的關鍵。一個在樹頂附近只花 O(1) 的檢查，可以抹去底部數以百萬計的候選。矛盾越早能被偵測到，我們就在樹上越高處下刀，省得也越多。
回溯法在約束滿足問題上最為耀眼——這類任務由每個解都必須遵守的規則來定義，例如「任兩個皇后不同列、不同行、不同對角線」，或是圖著色裡的「相鄰區域要塗不同顏色」。約束正是讓你能在部分候選上有東西可檢查的來源。約束越豐富、越早發揮作用，樹就被剪得越積極。一個幾乎沒有約束的問題，讓剪枝器無從下口，回溯法就退化回普通的列舉。
兩個經典範本：N 皇后與子集和
N 皇后問題是回溯法的教科書圖像。由上而下，每一列決定放一個皇后；每一層的選擇是放在哪一行。試探性地放下一個皇后後，拿它和上方已放好的皇后比對——同一行嗎？同一對角線嗎？若起衝突，那一行就不可行，它整棵子樹被跳過，連底下幾列都不必碰。只有當某列的皇后通過檢查，我們才下降到下一列。走過最後一列，就表示全部 n 個皇后和平共存：一個解。關鍵在於，衝突檢查只看到目前為止的部分棋盤，所以一個糟糕的第二列選擇會立刻被逮到，扼殺掉生成與測試法本會白白造出的所有更深層擺法。
子集和展示了第二種同樣常見的形狀。給定一些數字與目標 T，存在一個子集其和為 T 嗎？逐一決定每個數字；每一層的兩個子節點是「納入這個數字」或「排除它」——一棵深度 n、有 2^n 片葉子的二元樹。子集和的回溯用沿路徑攜帶的兩個廉價界限來剪枝：若當前和已超過 T（且數字皆非負），之後再納入任何數字都救不回來，於是停止；若當前和加上所有剩餘數字的總和仍不足 T，未來任何選擇都到不了目標，於是也停止。每個界限都砍掉一棵子樹。先把數字排序能讓這些界限更早咬住——一個微小的前處理步驟，磨利了底下每一次剪枝。
留意這兩者底下共用的骨架。有一個決定的排序（列；數字），每個決定有一小組選擇（行；納入／排除），一個對部分候選的廉價檢查，以及回程上的一次撤銷。把這四個欄位填好，你就有了一個幾乎能對付任何東西的回溯器——排列、組合、解謎器。難的從來不是遞迴；而是找出能盡早、盡廉價地偵測出絕路的可行性檢查。
超越可行性：定界，以及接下來是什麼
目前為止，剪枝器回答的是一個是非問題：這個前綴還能合法嗎？這對於「找任一個解」或「找全部解」十分完美。但許多任務想要的是最好的解，於是第二種更銳利的剪枝就變得可能。假設我們已經找到某個成本為 50 的有效候選。此刻我們正在探索一個部分候選，而我們能算出，即使在最樂觀的情況下，它最終的成本也不可能降到 60 以下。那麼這整條分支就毫無價值——它贏不過 50——於是即使它完全沒違反任何約束，我們也剪掉它。用一個樂觀的估計去和「目前最佳」比較來剪枝，正是從回溯法躍進到分支定界法的一步，也是下一篇指南的主題。
- 排好各個決定，並在目前的部分候選上，列出下一個決定的各種選擇。
- 對每個選擇，延伸候選，並對新的前綴跑可行性檢查。
- 若可行，就往更深處遞迴；若不可行，就跳過那個選擇的整棵子樹。
- 返回時，撤銷該選擇（還原先前的狀態）並移到下一個選擇；一個存活下來的完整候選就是一個解。
在繼續之前，再說一個誠實的提醒。你試各個選擇的順序、以及你固定各個決定的順序，都不是裝飾——它們可以讓執行時間相差好幾個數量級，因為它們決定了矛盾多快浮現、分支多早死去。「最受約束的變數優先」與「最不約束的值優先」是著名的啟發式法，但它們就是啟發式：通常有幫助的經驗法則，而非保證。無論如何，漸進的最壞情況依然是指數的。回溯法為你買到一棵剪去了可證明死路的樹；它買不到一個替本就沒有多項式時間解的問題硬湊出的多項式時間演算法。