回溯法——對部分解的深度優先搜尋（backtracking as DFS）

想像你在沒有地圖的情況下走迷宮。你一路向前，在每個岔口做選擇；走到死路時，你不會從頭來過——你退回最近一個還有沒試過岔路的路口，改走那條。這個退回的動作就是回溯。作為演算法，回溯一次做一個決定地建構解，而一旦某個部分選擇不可能通往任何好結果，它就撤銷最後那個選擇，改試下一個選項。

具體地說，回溯就是對部分解做深度優先搜尋。部分解是只建到一半的解——例如排列的前三個位置，或已擺好的前兩個皇后。演算法是遞迴的：若部分解已完整，就記錄下來；否則，對下一個決定的每個候選值，檢查加上它是否仍讓部分解可行；若可行，就加上、遞迴去做其餘決定，回來時再移除（撤銷），好讓下一個候選在乾淨狀態下被嘗試。這探索的是一棵節點為部分解、葉子為完整候選的樹，先深後廣——正是 DFS。「做—遞迴—撤銷」這個骨架在 N 皇后、子集合加總、圖著色與約束問題裡都一樣；只有可行性檢查會變。

整件事的重點、也是回溯勝過盲目列舉的原因，在於可行性檢查讓你能在延伸一個部分解之前就放棄它——一筆勾消一整棵候選子樹。若前兩個皇后已互相攻擊，你根本不會去擺其餘皇后，跳過底下所有葉子。最壞情況下回溯仍是指數的（當什麼都剪不掉時會退化成完整列舉），但在真實、受約束的實例上，剪枝往往把被探索的樹砍到極小的一部分，這正是它實用的原因。