引言
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：1、定义一个解空间，它包含问题的解。2、利用适于搜索的方法组织解空间。3、利用深度优先法搜索解空间。4、利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
基本思想
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。
回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。
回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，，剪去一些不可能到达 最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。
这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
经典示例1）八皇后问题#include <stdio.h>#include <math.h>int a[9] = {0};int n = 8, count = 0;//位置冲突算法 bool Chongtu(int a[], int n)//a[]位置数组，n皇后个数 {int i = 0, j = 0;for (i = 2; i <= n; ++i)//i：位置 for (j = 1; j <= i-1; ++j)//j：位置if ((a[i] == a[j]) || (abs(a[i]-a[j]) == i-j))//1：在一行；2：在对角线上return false; //冲突 return true;//不冲突 }//八皇后问题：回溯算法（递归版） void Queens8(int k) //参数k：递归摆放第k个皇后 {int i = 0;if (k > n)//k>n——即k>8表示最后一个皇后摆放完毕 {printf("第%d种情况：",++count);for (i = 1; i <= n; ++i)printf("%d ",a[i]);//打印情况 printf("\n");}else //8个皇后未全部摆放完毕{for (i = 1; i <= n; ++i)//摆放第k个皇后时（注释:转下一行） {//依次从列顶端开始搜索，一直到列底端，直到找到合适位置,如果未找到，自动返回上层递归(回溯)a[k] = i;if (Chongtu(a,k))//不冲突Queens8(k+1);//递归摆放下一个皇后}}return;}//主函数 int main(){Queens8(1);//参数1：表示摆放第1个皇后 return 0;} 更详细的八皇后问题说明，可以参考：经典算法——回溯（）
（未完待续……）
参考文献：
1）百度百科，回溯算法，
尝到你和你在一起的快乐，你是唯一能让我尝到酸甜苦辣的人。
