回溯法(back trace method)是一种有组织的系统化搜索技术，可以看作是蛮力法穷举搜索的改进。蛮力法穷举搜索首先生成问题的可能解，然后再去评估可能解是否满足约束条件。而回溯法每次只构造可能解的一部分，然后评估这个部分解，如果这个部分解有可能导致一个完整解，对其进一步构造，否则，就不必继续构造这个部分解了。回溯法常常可以避免搜索所有的可能解，所以，它适用于求解组合数量较大的问题。
概述
解空间树的动态搜索
蛮力法是对整个解空间树中的所有可能解进行穷举搜索的一种方法，但是，只有满足约束条件的解才是可行解，只有满足目标函数的解才是最优解，这就有可能减少搜索空间。回溯法从根节点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该节点为根的子树的搜索，即所谓剪枝（pruning);否则，进入以该节点为根的子树，继续按照深度优先策略搜索。
回溯法的求解过程
由于问题的解向量$X=(x_1,x_2,...,x_n)$中每个向量$x_i(1 \leq i \leq n)$都属于一个有限集合$Si={a{i1},a{i2}...,a{ir_i}}$,因此，回溯法可以按某种顺序（如字典序）依次考察笛卡尔积$S_1 \times S_2 \times ... \times S_n$中的元素。初始时，令解向量X为空，然后，从根节点出发，选择$S_1$的第一个元素作为解向量X的的第一个分量，即$x1 = a{11}$,如果$X=(x_1)$是问题的部分解，则继续扩展解向量X，选择$S_2$的第一个元素作为解向量X的第二个分量，否则，选择$S_1$的下一个元素作为解向量X的第一个分量，即$x1 = a{12}$。以此类推，一般情况下，如果$X=(x_1,x_2,...,xi)$是问题的部分解，则选择$S{i+1}$的第一个元素作为解向量X的第i+1个分量时，有下面三种情况：
(1)如果$X=(x_1,x2,...,x{i+1})$是问题的最终解，则输出这个解。如果问题只希望得到一个解，就结束搜索，否则继续搜索其他解。
(2)如果$X=(x_1,x2,...,x{i+1})$是问题的部分解，则继续构造解向量的下一个分量。
(3)如果$X=(x_1,x2,...,x{i+1})$既不是问题的部分解，也不是问题的最终解，则存在下面两种情况：
-
如果$x{i+1} = a{i+1k}$不是集合$S{i+1}$的最后一个元素，则令$x{i+1} = a_{i+1 k+1}$,即选择$S_i+1$的下一个元素作为解向量X的第i+1个分量；
-
如果$x{i+1} = a{i+1k}$是集合$S_{i+1}$的最后一个元素，就回溯到$X=(x_1,x_2,...,x_i)$，选择$S_i$的下一个元素作为解向量X的第一个分量，假设$xi = a{ik}$，如果$a_{ik}$不是集合$S_i$的最后一个元素，则令$xi = a{ik+1}$;否则，就继续回溯到$X=(x_1,x2,...,x{i-1})$。
回溯算法的一般框架：
主算法
X = {}
flag = false;
advance(1);
if(flag)
输出解X
else
输出无解
advance(int k)
{
对每一个x在Sk循环执行下列操作
xk = x
将xk加入X
if(X是最终解) flag = true; return;
else if(X是部分解)
advance(k+1)
}回溯法的非递归迭代形式的一般框架如下：
X = {}
flag = flase
k = 1
while(k >=1)
当（Sk没有被穷举）循环执行下列操作
xk=Sk中的下一个元素
将xk加入X
if(X为最终解)
flag = true
break
else(X为部分解)
k = k+1
continue
k = k - 1
if flag输出解X
else
输出无解典型问题
八皇后问题
八皇后问题是19世纪著名数学家高斯于1850年提出。问题是：在8*8的棋盘上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或统一斜线上。可以把八皇后问题扩展到n皇后问题，即在n*n的的期盼上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上。
显然，棋盘的每一行上可以而且必须摆放一个皇后，所以，n皇后问题的可能解用一个n元向量$X=(x_1,x_2, ...x_n)$表示，其中，$1 \leq i \leq n$，并且$1 \leq x_i \leq n$, 即第i个皇后放在第i行第$x_i$列上。
由于两个皇后不能位于同一列上，所以解向量X必须满足约束条件：
x_i \neq x_j若两个皇后摆放的位置分别为$(i,x_i)$和$(j,x_j)$,在棋盘上斜率为-1的斜线上，满足条件$i-j = x_i - x_j$,在棋盘上斜率为1的斜线上，满足条件$i+j = x_i + x_j$,综合两种情况，由于两个皇后不能位于同一个斜线上，所以，解向量X必须满足约束条件：
|i - x_i| \neq | j - x_j|八皇后问题的参考代码:
#include <stdio.h>
#include <math.h>
int x[20] = {0};
//考察皇后k放置在x[k]列是否发生冲突
int Place(int k)
{
int i = 0;
for(i = 0; i < k; i++)
{
if(x[k] == x[i] || (abs(k-i) == abs(x[k] - x[i])))
return 0;
}
return 1;
}
void Queue(int n)
{
int i = 0;
int j = 0;
int k = 0;
//初始化
for(i = 1; i <= n; i++)
x[i] = 0;
k = 1;
while(k >= 1)
{
x[k] = x[k] + 1; //在下一列放置第k个皇后
while(x[k] <= n && !Place(k))
x[k] = x[k] + 1; //搜索下一列
if(x[k] <= n && k == n) //得到一个解，输出
{
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
if(j == x[i])
printf(" Q ");
else
printf(" x ");
}
printf("\r\n");
}
return;
}
else if(x[k] <= n && k < n)
{
//放置下一个皇后
k = k + 1;
}
else
{
x[k]= 0; //重置x[k], 回溯
k = k - 1;
}
}
}
int main(int argc, const char * argv[]) {
Queue(4);
return 0;
}输出为:
x Q x x
x x x Q
Q x x x
x x Q x 找了个比较好的博文可以参考下：
八皇后问题
回溯法解全排列问题
#include <stdio.h>
int array[10] = {0};
int count = 0;
void permutation(int *array, int begin_index, int length)
{
int i = 0;
int tmp;
if(begin_index == length)
{
for(i = 0; i < length; i++)
{
printf("%d\t", array[i]);
}
printf("\r\n");
count++;
}
else
{
for(i = begin_index; i < length; i++)
{
tmp = array[begin_index];
array[begin_index] = array[i];
array[i] = tmp;
permutation(array, begin_index+1, length);
tmp = array[begin_index];
array[begin_index] = array[i];
array[i] = tmp;
}
}
}
int main(int argc, const char * argv[]) {
int i = 0;
int n = 10;
for(i = 0; i < n; i++)
{
array[i] = i;
}
permutation(array, 0, n);
printf("\r\ncount of array:%d\r\n", count);
return 0;
}