回溯法
对于回溯法，网上有很多种解释，这里我依照自己的（死宅）观点做了以下三种通俗易懂的解释：
- 正经版解释：其实人生就像一颗充满了分支的n叉树，你的每一个选择都会使你走向不同的路线，获得不同的结局。如果能重来，我要选李白~呸！说错了，如果能重来，我们就能回溯到以前，选择到最美好的结局。
- 游戏版解释：玩过互动电影游戏（如 行尸走肉）的都知道，你的每个选择都会影响游戏的结局，掌控他人的生死。每次选择错误导致主角或配角死亡，我们是不是回溯读档，希望得到一个更好的结局。PS：克莱曼婷天下无敌！
- 动漫版解释：看过主角拥有死亡回归（疯狂暗示486）的都知道，主角的每个选择都能影响大局，可是486直接能回溯重选，这与我们今天要讲的回溯法极其相似。PS：爱蜜莉雅、雷姆我都要！
专业名词
- 解空间： 即 所有的可能情况
概念
回溯算法：是类似于枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
它是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为 回溯法 ，而满足回溯条件的某个状态的点称为 “回溯点” （你也可以理解为 存档点 ）。
上图为八皇后的解空间树， 如果当前点不符合要求就退回再走 。
许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
基本思想
在包含问题的所有解的解空间树中，按照 深度优先搜索 的策略，从根结点出发深度探索解空间树。
当探索到某一结点时，要先判断该结点是否包含问题的解：
- 如果 包含 ，就从该结点出发继续探索下去；
- 如果该结点 不包含 问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）
结束条件：
- 若用回溯法求问题的 所有解 时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
- 若使用回溯法求 任一个解 时，只要搜索到问题的一个解就可以结束。
网上的一般步骤
虽然我觉得网上的一般步骤太抽象了，但是还是摆在这里供大家参考吧。。
- 针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
- 确定结点的扩展搜索规则：及时确定规则，并不是每个解空间都要走完才能发现是死路的，有时候走到一半就发现不满足条件了。
- 以深度优先方式搜索解空间，并在搜索过程中 用剪枝函数避免无效搜索：不满足条件的路径及时剪掉（即 剪枝），避免继续走下去浪费时间。类比：比如说 削苹果 ，我们规定：苹果皮必须不断，要完整地削完整个苹果。那么，如果我们削到一半苹果皮断掉了，我们就可以直接退回去（即 回溯）换个苹果削了，如果继续削下去，只会浪费时间。
算法框架
问题框架：
设问题的 解 是一个 n维向量(a1,a2,………,an) ， 约束条件 是 ai(i=1,2,3,…..,n)之间 满足某种条件，记为 f(ai) 。
非递归回溯框架
其中， a[n] 为解空间， i 为搜索的深度，框架如下：
int a[n],i; //a[n]为解空间，i为深度
初始化数组 a[];
i = 1;
while (i>0(有路可走) and (未达到目标)) { //还未回溯到头
if(i > n) { //搜索到叶结点
搜索到一个解，输出；
} else { //处理第 i 个元素
a[i]第一个可能的值；
while(a[i]在不满足约束条件且在搜索空间内) {
a[i]下一个可能的值；
}//while
if(a[i]在搜索空间内) {
标识占用的资源；
i = i 1; //扩展下一个结点
} else {
清理所占的状态空间； //回溯
i = i – 1;
}//else
}//else
}//while
递归回溯框架
回溯法是对解空间的 深度优先搜索 ，在一般情况下使用 递归函数 来实现回溯法比较简单。
其中， a[n] 为解空间， i 为搜索的深度，框架如下：
int a[n]; //a[n]为解空间
BackTrace(int i) { //尝试函数，i为深度
if(i>n) {
输出结果;
} else {
for(j = 下界; j <= 上界; j=j 1) { //枚举 i 所有可能的路径
if(check(j)) { //检查满足限界函数和约束条件
a[i] = j;
... //其他操作
BackTrace(i 1);
回溯前的清理工作（如 a[i]置空值等）;
}//if
}//for
}//else
}//BackTrace
回溯四步走
由于上述网上的步骤太抽象了，所以在这里我自己总结了回溯四步走：
- 编写检测函数：检测函数用来检测此路径是否满足题目条件，是否能通过。这步不做硬性要求。。不一定需要
- 明确函数功能：要清楚你写这个函数是想要做什么；
- 寻找递归出口：一般为某深度，或叶子节点。
- 明确所有路径（选择） ： 这个构思路径最好用 树形图 表示。例如：走迷宫有上下左右四个方向，也就是说我们站在一个点处有四种选择，我们可以画成无限向下延伸的四叉树。直到向下延伸到叶子节点，那里便是出口；从根节点到叶子节点沿途所经过的节点就是我们满足题目条件的选择。
- 回溯还原现场：若 该节点所有选择已做完却仍然没有找到出口 ，那么我们需要 回溯还原现场 ，将该节点重置为初始状态，回溯到一切都没有发生的时候，再退回去。注意：回溯还原现场是必要的，如果不还原现场，那你的回溯有什么意义呢。。类比：大雄出意外了，哆啦A梦坐时空机回到过去想要改变这一切，结果过去的一切都没有被重置到初始状态，回到过去大雄还是现在这种受伤的样子没有改变，那么回到过去有什么意义呢。
编写检测函数（非必须）
第一步，写出检测函数，来检测这个路径是否满足条件，是否能通过。
这个函数依据题目要求来编写，当然，如果要求不止一个，可能需要编写多个检测函数。
例如：凑算式
这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。
比如：
6 8/3 952/714 就是一种解法，
5 3/1 972/486 是另一种解法。
这个算式一共有多少种解法？
要做出这个题，
第一步，要写出检测函数
public static int sum = 0; // 用来存放总共的解法数
public static double[] a = new double[10];
// 判断数组里前j个元素是否与t相同
/**
* @param a 传入一个数组a
* @param j 判断前j个元素
* @param t 是否与t相同
* @return
*/
public static boolean same(double[] a, int j, int t) {
for (int i = 1; i < j; i ) {
if (a[i] == t) {
return true;
}
}
return false;
}
/**
* @param a 判断a数组是否满足表达式
* @return 如果满足就true，不满足就false
*/
public static boolean expression(double[] a) {
if ((a[1] a[2] / a[3] (a[4] * 100 a[5] * 10 a[6]) / (a[7] * 100 a[8] * 10 a[9]) == 10))
return true;
else
return false;
}
明确函数功能
由于此题要填数字，所以我们定义choose(i)的含义为：在算式中自动填入数字 i 。
寻找递归出口
第二步，要寻找递归出口，当1~9均已填入后，判断表达式是否成立，若成立，则输出。
// 如果选择的数字大于9，则代表1~9均已选完，判断是否满足表达式，输出选择的表达式
if (i > 9) {
if (expression(a)) {
for (int x = 1; x < 10; x ) {
System.out.print(a[x] " ");
}
System.out.println();
sum ;
}
return;
}
明确所有路径
第三步，要知道这个递归是几个选择，即 几叉树。
此题为1~9九个选择，九条路，九叉树。
for (int j = 1; j <= 9; j ) {
// 如果将要填入的数与前面不冲突，则填入
if (!same(a, i, j)) {
a[i] = j;
choose(i 1);
}
}
回溯还原现场
第四步，若该节点没有找到出口，则将当前位置回溯，还原现场，重新选择
在本题中， 还原现场 即 重置为0（表示还未填入1~9的数字）
for (int j = 1; j <= 9; j ) {
// 如果将要填入的数与前面不冲突，则填入
if (!same(a, i, j)) {
a[i] = j;
choose(i 1);
//若没有找到出口，则将当前位置重置为0，回溯，还原现场
a[i] = 0;
}
}
实例
凑算式
这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。
比如：
6 8/3 952/714 就是一种解法，
5 3/1 972/486 是另一种解法。
这个算式一共有多少种解法？
答案：
// 凑算式
public class Sy1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
choose(1);
System.out.println("一共" sum "种解法");
}
public static int sum = 0; // 用来存放总共的解法数
public static double[] a = new double[10];
// 判断数组里前j个元素是否与t相同
/**
* @param a 传入一个数组a
* @param j 判断前j个元素
* @param t 是否与t相同
* @return
*/
public static boolean same(double[] a, int j, int t) {
for (int i = 1; i < j; i ) {
if (a[i] == t) {
return true;
}
}
return false;
}
/**
* @param a 判断a数组是否满足表达式
* @return 如果满足就true，不满足就false
*/
public static boolean expression(double[] a) {
if ((a[1] a[2] / a[3] (a[4] * 100 a[5] * 10 a[6]) / (a[7] * 100 a[8] * 10 a[9]) == 10))
return true;
else
return false;
}
/**
* @param i 选择第i个数字 递归
*/
public static void choose(int i) {
// 如果选择的数字大于9，则代表1~9均已选完，输出选择的表达式
if (i > 9) {
if (expression(a)) {
for (int x = 1; x < 10; x ) {
System.out.print(a[x] " ");
}
System.out.println();
sum ;
}
return;
}
for (int j = 1; j <= 9; j ) {
// 如果将要填入的数与前面不冲突，则填入
if (!same(a, i, j)) {
a[i] = j;
choose(i 1);
//若没有找到出口，则将当前位置重置为0，回溯，还原现场
a[i] = 0;
}
}
}
}
程序运行结果：
3.0 5.0 1.0 9.0 7.0 2.0 4.0 8.0 6.0
4.0 9.0 3.0 5.0 2.0 8.0 1.0 7.0 6.0
5.0 3.0 1.0 9.0 7.0 2.0 4.0 8.0 6.0
5.0 4.0 3.0 7.0 2.0 6.0 1.0 9.0 8.0
5.0 4.0 9.0 7.0 3.0 8.0 1.0 6.0 2.0
5.0 8.0 6.0 4.0 7.0 3.0 1.0 2.0 9.0
6.0 4.0 2.0 3.0 5.0 8.0 1.0 7.0 9.0
6.0 4.0 2.0 7.0 1.0 8.0 3.0 5.0 9.0
6.0 7.0 3.0 4.0 8.0 5.0 2.0 9.0 1.0
6.0 8.0 3.0 9.0 5.0 2.0 7.0 1.0 4.0
6.0 9.0 8.0 4.0 3.0 7.0 1.0 5.0 2.0
7.0 1.0 4.0 9.0 6.0 8.0 3.0 5.0 2.0
7.0 3.0 2.0 8.0 1.0 9.0 5.0 4.0 6.0
7.0 3.0 2.0 9.0 8.0 1.0 6.0 5.0 4.0
7.0 5.0 3.0 2.0 6.0 4.0 1.0 9.0 8.0
7.0 5.0 3.0 9.0 1.0 2.0 6.0 8.0 4.0
7.0 9.0 6.0 3.0 8.0 1.0 2.0 5.0 4.0
7.0 9.0 6.0 8.0 1.0 3.0 5.0 4.0 2.0
8.0 1.0 3.0 4.0 6.0 5.0 2.0 7.0 9.0
8.0 6.0 9.0 7.0 1.0 2.0 5.0 3.0 4.0
8.0 7.0 6.0 1.0 9.0 5.0 2.0 3.0 4.0
9.0 1.0 3.0 4.0 5.0 2.0 6.0 7.0 8.0
9.0 1.0 3.0 5.0 2.0 4.0 7.0 8.0 6.0
9.0 2.0 4.0 1.0 7.0 8.0 3.0 5.0 6.0
9.0 2.0 4.0 3.0 5.0 8.0 7.0 1.0 6.0
9.0 3.0 4.0 1.0 5.0 7.0 6.0 2.0 8.0
9.0 4.0 8.0 1.0 7.0 6.0 3.0 5.0 2.0
9.0 4.0 8.0 3.0 5.0 6.0 7.0 1.0 2.0
9.0 6.0 8.0 1.0 4.0 3.0 5.0 7.0 2.0
一共29种解法
方格填数
如下的10个格子填入0~9的数字。
