可行性剪枝（feasibility pruning）

想像你打包行李箱，一件件試著放，而一旦蓋子關不上，你就停止再加東西，而不是把這個注定失敗的嘗試做完。可行性剪枝就是把這份直覺化為演算法：一旦某個部分解已經違反約束，你就拒絕它，並跳過完成它的每一種方式。你不必等候選做完才發現它早已無望——你提早把它砍斷。

在狀態空間樹裡，部分解是一個節點，它可能的完成方式是它底下的子樹。可行性剪枝之所以有效，靠的是一種單調性：對許多約束來說，一旦被某個部分解違反，無論你再加什麼都仍然違反。兩個已互相攻擊的皇后，在你擺更多皇后後仍互相攻擊；一個已超過目標總和的部分子集合（且只剩非負物品可加）永遠回不到目標以下。所以若節點不可行，它子樹中的每個葉子也都不可行，剪枝便是可靠的——你絕不會丟掉一個真正的解。具體地說，在回溯遞迴中你在遞迴前插一個檢查：若加上這個選擇會違反約束，就不對它遞迴，直接換下一個候選。

省下的功夫來自樹的形狀：在靠近根處砍掉一個節點，就刪去一整棵指數級的子樹，所以即使是不起眼的剪枝，也能把實際執行時間從「不可能」變成「瞬間」。這正是為什麼配上好的可行性檢查的回溯，能例行地解出盲目列舉碰都碰不了的 N 皇后或數獨。誠實的提醒：剪枝只在約束真的「早早咬人」時才有幫助，最壞情況下（約束很少或很晚才生效）樹幾乎沒被修掉，你又回到指數時間。