背景介绍：回溯法是一种穷举类型的算法，与其说它是一种算法，倒不如说它是一种试法。回溯法并没有什么高深的算法思想，虽然名字起的很高规格，但其实它的算法性连二分查找都比不上。这里说的算法性其实就是指技巧性，对问题特性了解越深入，越能创造出很巧妙的算法，在时间复杂度的级别上提高算法效率。这体现了算法效率与适用性之间的矛盾，二分查找效率很高，但适用性比较低，类似的还有著名的KMP算法。而穷举法效率最低，但几乎适用于所有问题。

好像有点儿扯远了，我们还是接着说回溯法。回溯法是一种试探性算法，从这一点上看，它很像穷举法。但它终究不是穷举法，回溯法是有组织的进行穷举，在试探过程中不断通过题设要求减少搜索空间，而这种减少不是一个一个解的减少，而是对搜索空间进行大规模剪枝，从而使得实际搜索空间远远小于问题的解空间，所以回溯法的实际运行效率还是比较高的。

应用场景：回溯法的应用背景说大很大，说小很小。算法大都在“不得不”的情况 下才会使用，如果有别的算法，那它很有可能比回溯法高效，别忘了，回溯法是基于穷举的。回溯法适用于解排列组合类问题，也就是说目标解是从一个候选空间中选择出来的。从数量级上考虑，设候选空间的大小为n，如果选择是可重复的，那生成的搜索树为完全n叉树，搜索空间为n^n（如0-1背包问题，生成的解空间为高度为n完全二叉树，其中n为物体个数）。如果选择不能重复，那生成的解空间为n!(如TSP问题生成的解空间为n!,其中n为城市个数)。也就是说，当我们通过分析发现问题的解空间为n^n或者n!时，那很可能要用到我们的回溯法了。

搜索策略：要用回溯法解决问题，那首先要确定问题的状态空间树。这个并不是很难，就看每一步选择有多少个可选值就可以了，第一步有8个可选值，那树第一层就有8个节点，第二步有5个可选值，那第一层每个节点都有5个分支，则第二层有8×5=40个节点，以此类推……到第n层一共有m1×m2×……×mn个节点，其中mi为第i步的可选值的个数。

确定了状态空间树，那下一步就是搜索了。这时候就体现出回溯法的优势了，前面不是说了嘛，回溯法的特点就是有规律、有组织的进行搜索，那下面就来看一下回溯法是如何进行搜索的：（PS：这部分内容大都取自清华大学郑宗汉的《算法设计与分析》一书，当然也有自己的一些理解）在开始搜索之前，我们先来说一下我们要做的事情，我们要得到一个解向量solution，每个分量对应每一步选择的结果，显然这个解向量的长度应该为n（我们采用C语言的标准，下标范围为0到n-1）。好了，现在我们有了一个状态空间树（逻辑上的，并不用实现）和一个解向量（物理上的，要用来装数据的）。现在可以开始搜索了，先设定一个下标r，这个r就是解向量的下标，也用于标识状态树的第r行。先做第一步，令r=0，选solution[0]，也就是从树的第0行选择一个值放入solution[0]，显然刚开始我们应该选择第一个，即前面提到的8个里面的第一个。然后看这个半成品解向量是否是可行的，也就是说看看刚才选择的那个值是否满足要求，加入那个值不满足要求，那应该选择第二个，以此类推直到选择一个可行的值，放入solution[0]。然后r++进行第二步，选择solution[1]，同样的，我们应该从树的第二行中选择第一个看构成的解是否可行（此时解向量中包含两个元素），这样的步骤一直进行下去，直到出现这样的情况

（1）r=n-1了，也就是说我们得到了问题的一个可行解，这时候就要看题设要求了，如果只要求找到一个可行解，那此时算法就可以停止了。

（2）某一层的候选值选完了，我们知道，没一层的候选值都有一定个数，如上面提到的例子中第二层只有5个候选值，如果这五个候选值都试探完了还是没有可行解那该怎么办呢？这里体现的思想就是我们回溯法名字的由来，回溯。也就是令r--退回去，从新选择上面的解。比如上面的例子先选择8个中的第一个作为解的一部分，然后发现后面的5个和前面这个都不能组成可行解，那这就说明前面那个选择是不可行的，和后面是不搭配的。所以应该返回去选择8个中的第二个，然后再对5个进行选择，看哪个与这个第二个想匹配。

（3）最后一种情况，因为我们这个过程中有回溯过程，即r--的过程，那可能最后r小于0了，这说明整个树都搜索完了，也就是问题没有可行解。

代码实现：回溯法一般有两种代码实现方案，递归方法和非递归方法。相比之下，递归设计方法比较简单，用前面提到的r作为递归变量即可，如果满足搜索条件，则递归调用r+1对应函数，如果不满足，则递归调用r-1对应的函数。基础步为当r＜0或r=n-1分别对应无解和得到可行解，这个就不多说了。非递归方法，也就是循环方法设计细节比较多，但只要掌握了其特点，对不同问题的适用性很强（即代码只通过很少的修改就可以应用到不同问题），加之其效率高于递归算法（循环的优势），所以这里我们着重讲一下回溯的非递归代码实现。

先看一下最终代码吧：

<pre name="code" class="cpp">void backtrack_item()
{
	initial(x);//初始化解向量
	i = 0; k[i] = 1; flag = false;//初始化
	while(i>=0){//当行数大于0时做
		while(k[i]<m[i]){
			x[i] = get(i,k[i]);//得到选择元素
			if(constrain(x) && bound(x)){//是可行解
				if(solution(x)){//是最终解
					flag = true;break;
				}
				else{//不是最终解
					i = i+1;k[i] = 0;
				}
			}
			else{//不是可行解
				k[i]=k[i]+1;
			}
		}
		if(flag) break;
		k[i]=1;i = i-1;k[i]=k[i]+1; //回溯
	}
	if(!flag){//无解
		initial(x);//重置解向量
	}
}

<pre name="code" class="cpp">bool placeOk(int *p,const int n)
{
	for(int i=0;i<n;i++){
		if(p[i]==p[n] || abs(i-n)==abs(p[i]-p[n]))
			return false;
	}
	return true;
}

void queens_n(const int n)
{
	int *x = new int[n];
	for(int j=0;j<n;j++){//初始化解向量
		x[j] = 1;
	}
	int i = 0; bool flag = false;//初始化
	while(i>=0){
		while(x[i]<=n){
			if(placeOk(x,i) ){//得到可行解
				if(i==n-1) {flag=true; break;}//得到最终可行解，退出
				else{//得到部分可行解，搜索下一行
					i++; x[i]=1;
				}
			}
			else{//当前解不可行
				x[i]++;
			}
		}
		if(flag) break;
		x[i]=1;i--;x[i]++;//回溯
	}
	//省去了重新初始化，直接释放内存
	if(!flag) cout<<"没有可行解！"<<endl;
	else{
		for(int i=0;i<n;i++){
			cout<<x[i]<<" ";
		}cout<<endl;
	}
	delete[] x;
}

<pre name="code" class="cpp">bool placeOk(int *x,int k,int **c,int n)
{
	//自己可实现
}
bool m_colouring(int n,int m,int x[],int **c)
{
	//输入：n为顶点个数，m为颜色种类，x为解向量，c为邻接矩阵
	for(int i=0;i<n;i++) x[i]=0;//初始化解向量
	int i = 0; bool flag = false;//初始化
	while(i>=0){
		while(x[i]<=m){
			if(placeOk(x,i,c,n)){//得到可行解
				if(i==n-1) {flag=true; break;}//得到最终可行解，退出
				else{//得到部分可行解，搜索下一行
					i++; x[i]=0;
				}
			}
			else{//当前解不可行
				x[i]++;
			}
		}
		if(flag) break;
		x[i]=0;i--;x[i]++;//回溯
	}
	if(flag)return true;
	else return false;

}