用搜尋做圖著色（graph coloring by search）

想像一張地圖，你必須替每個國家著色，使任兩個共享邊界的國家不同色，並盡量用最少的顏色。把國家抽象成點（頂點）、把共享邊界抽象成線（邊），你就得到圖著色：替每個頂點指定一種顏色，使每條邊的兩個端點不同色。k 著色問題問的是：只用 k 種顏色能不能做到。

搜尋一個著色就是在 CSP 上回溯。變數是頂點，每個的值域是 k 種顏色，每條邊是一條「它兩端點須不同」的約束。以某個順序處理頂點；對當前頂點試每種顏色，遞迴之前先檢查它與任何已著色的鄰居都不衝突。若某顏色合法，就指派並遞迴到下一個頂點；若沒有合法顏色，就回溯到前一個頂點、試它的下一種顏色。可行性檢查（這顏色和鄰居撞了嗎？）剪得很狠：一個糟糕的早期顏色可能讓一整片區域無法著色，立刻偵測到就砍掉它底下的每一種完成方式。好的頂點排序幫助很大——先替最受約束的頂點著色，往往能盡早失敗、剪得更多。

圖著色是經典的 NP 完全問題（判定 3 著色性就已經是 NP 完全），所以沒有已知演算法能快速替每張圖著色，而回溯搜尋在最壞情況下是指數的。但它在實務上極其有用，正是因為那些會出現的有結構案例：編譯器的暫存器配置（同時存活的變數必須分到不同暫存器）、排程（重疊的事件需不同時段）、頻率指派全都歸約成著色，而剪枝後的搜尋能處理真實實例，那是「列舉所有 2^n 式著色」永遠辦不到的。