約束滿足問題（constraint satisfaction problem）

許多謎題有著相同的形狀：你有一組空格要填，每個空格能放幾個值之一，而某些規則規定哪些組合是允許的。數獨（81 格、值 1-9、每列每行每宮不得重複）、地圖著色（每個區域上一種顏色、相鄰須不同）、排程（每個任務分到一個時段、衝突的任務不得重疊），都是同一類問題換了不同外衣。那個共同的形狀就是約束滿足問題。

正式地說，一個 CSP 有三個部分：一組變數、每個變數的允許值域，以及一組約束，每條禁止某些變數上的某些值組合。解是替每個變數各指定一個值，使得沒有任何約束被違反。自然的暴力法是對所有指派做完全列舉——若有 n 個變數各有 d 個可能值，那就是 d^n 種組合，呈指數。但 CSP 正是回溯的主場：一次指派一個變數，每次指派後檢查那些已完全確定的約束；若有任何被違反，就剪枝並回溯。因為單一個壞指派就能排除一大片完成方式，可行性剪枝在這裡效果驚人。

CSP 之所以重要，一是因為這種表述無所不在——N 皇后、圖著色、字謎算術（cryptarithmetic）、型別推論、排課全都是 CSP——二是因為這種表述帶來了超越純回溯的豐富工具箱：約束傳播（在猜之前先推出被強迫的值，就像在數獨上做鉛筆標記），以及變數與值的排序啟發式（先指派最受約束的變數以盡早失敗）。誠實的事實是：一般的 CSP 是 NP 困難的，所以沒有任何方法對每個實例都快；那些啟發式讓典型、有結構的實例變得可解，而非全部。