回溯法（英語：backtracking）是暴力搜索法中的一種。 對于某些計算問題而言，回溯法是一種可以找出所有（或一部分）解的一般性算法，尤其適用于約束滿足問題（在解決約束滿足問題時，我們逐步構造更多的候選解，并且在確定某一部分候選解不可能補全成正確解之后放棄繼續搜索這個部分候選解本身及其可以拓展出的子候選解，轉而測試其他的部分候選解）。 <br> 在經典的教科書中，八皇后問題展示了回溯法的用例。（八皇后問題是在標準國際象棋棋盤中尋找八個皇后的所有分布，使得沒有一個皇后能攻擊到另外一個。） <br> 回溯法采用試錯的思想，它嘗試分步的去解決一個問題。在分步解決問題的過程中，當它通過嘗試發現現有的分步答案不能得到有效的正確的解答的時候，它將取消上一步甚至是上幾步的計算，再通過其它的可能的分步解答再次嘗試尋找問題的答案。回溯法通常用最簡單的遞歸方法來實現，在反復重復上述的步驟后可能出現兩種情況： 找到一個可能存在的正確的答案 在嘗試了所有可能的分步方法后宣告該問題沒有答案 在最壞的情況下，回溯法會導致一次復雜度為指數時間的計算。 <br> 算法架構： <br> 非遞歸回溯框架 ``` int a[n],i; 初始化數組a[]; i = 1; while (i>0(有路可走) and (未達到目標)) // 還未回溯到頭 { if(i > n){ 搜索到一個解，輸出； } else { // 處理第i個元素 a[i]第一個可能的值； while(a[i]在不滿足約束條件且在搜索空間內){ a[i]下一個可能的值； } if(a[i]在搜索空間內){ 標識占用的資源； i = i+1; // 擴展下一個結點 } else { 清理所占的狀態空間； // 回溯 i = i –1; } } } ``` 遞歸的算法框架 ``` int a[n]; try(int i) { if(i>n) { 輸出結果; } else { for(j = 下界; j <= 上界; j=j+1) { // 枚舉i所有可能的路徑 if(fun(j)){ // 滿足限界函數和約束條件 a[i] = j; ... // 其他操作 try(i+1); 回溯前的清理工作（如a[i]置空值等）; } } } } ```