來源
用回溯算法解決問題的一般步驟：
1、針對所給問題，定義問題的解空間，它至少包含問題的一個（最優）解。
2、确定易于搜索的解空間結構,使得能用回溯法方便地搜索整個解空間。
3、以深度優先的方式搜索解空間，并且在搜索過程中用剪枝函數避免無效搜索。
問題的解空間通常是在搜索問題解的過程中動态産生的，這是回溯算法的一個重要特性。
确定了解空間的組織結構後，回溯法就從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，并成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。此時，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。
基本思想
回溯算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。八皇後問題就是回溯算法的典型，第一步按照順序放一個皇後，然後第二步符合要求放第2個皇後，如果沒有位置符合要求，那麼就要改變第一個皇後的位置，重新放第2個皇後的位置，直到找到符合條件的位置就可以了。回溯在迷宮搜索中使用很常見，就是這條路走不通，然後返回前一個路口，繼續下一條路。回溯算法說白了就是窮舉法。不過回溯算法使用剪枝函數，剪去一些不可能到達最終狀态（即答案狀态）的節點，從而減少狀态空間樹節點的生成。回溯法是一個既帶有系統性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，隻要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的算法稱為回溯法，它适用于解一些組合數較大的問題。
算法框架
（pascal語言）
procedure try(i:integer);
var
begin
if i>n then 輸出結果
else for j:=下界 to 上界 do
begin
x[i]:=h[j];
if 可行{滿足限界函數和約束條件} then begin 置值；try(i+1); end;
end;
（c++）以下以一道題目為例，素數環問題
将從1到n這n個整數圍成一個圓環，若其中任意2個相鄰的數字相加，結果均為素數，那麼這個環就成為素數環。
#include
#include
#include
using namespace std;
int ans[21] = {0}, tot = 0;
bool a[21] = {0};
void print(){
tot++;
cout << "No." << tot << ':';
for (int i = 1; i <= 20; i++)
cout << ans[i] << ' ';
cout << endl;
}
bool isprime(int x1, int x2){
int i = x1 + x2,f;
for (f = 2; f <= sqrt(i); f++)
if (i % f == 0)
return false;
return true;
}
int search(int t){
for (int i = 1; i <= 20; i++){
if (a[i] == false && isprime(ans[t - 1], i)){
ans[t] = i;
a[i] = true;
if (t == 20 && isprime(ans[1], ans[20]))
print();
else
search(t + 1);
a[i] = false;
}
}
}
int main() {
search(1);
printf("The total is %d", tot);
}
典型例題
問題描述
八皇後問題：在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處于同一行、同一列或同一斜線上，問有多少種擺法。
代碼
int g_number = 0;
void EightQueen()
{
const int queens = 8;
int ColumnIndex[queens];
for(int i = 0; i < queens; ++ i)
ColumnIndex[i] = i;
Permutation(ColumnIndex, queens, 0);
}
void Permutation(int ColumnIndex[], int length, int index)
{
if(index == length)
{
if(Check(ColumnIndex, length))
{
++ g_number;
PrintQueen(ColumnIndex, length);
}
}
else
{
for(int i = index; i < length; ++ i)
{
int temp = ColumnIndex[i];
ColumnIndex[i] = ColumnIndex[index];
ColumnIndex[index] = temp;
Permutation(ColumnIndex, length, index + 1);
temp = ColumnIndex[index];
ColumnIndex[index] = ColumnIndex[i];
ColumnIndex[i] = temp;
}
}
}
bool Check(int ColumnIndex[], int length)
{
for(int i = 0; i < length; ++ i)
{
for(int j = i + 1; j < length; ++ j)
{
if((i - j == ColumnIndex[i] - ColumnIndex[j])
|| (j - i == ColumnIndex[i] - ColumnIndex[j]))
return false;
}
}
return true;
}
void PrintQueen(int ColumnIndex[], int length)
{
printf("Solution %dn", g_number);
for(int i = 0; i < length; ++i)
printf("%dt", ColumnIndex[i]);
printf("n");
}
