回溯法是一种搜索算法，从某一起点出发按一定规则探索，当试探不符合条件时则返回上一步重新探索，直到搜索出所求的路径。
回溯法所求的解可以看做解向量(n皇后坐标组成的向量，迷宫路径点组成的向量等)，所有解向量的几何称为解空间。理论上说，回溯法可以遍历有限个解组成的解空间。
首先介绍回溯法中所需的几个要素：
- 起点
解向量中第一个元素，第一个可能取得的值。 如迷宫的起点或者假设第一个皇后在(1,1)的位置。
- 遍历解向量中下一个元素所有可能取值的方法
如迷宫中四个方向沿顺时针试探，n皇后中行优先遍历二维数组。
一般需要记录当前遍历的进度(n皇后中上一行皇后的列号，迷宫路径栈顶的方向), 便于回溯后再次试探跳过已试探过的路径。
若从头开始重新试探则会陷入【试探--下一位置的下一位置无解-回溯-重新试探】的死循环。(这种时候就显示出yield的优越性了)
- 判断某一取值是否可行
如n皇后中判断是否冲突的函数，迷宫中判断是否可通
- 判断是否找到一个解和全部解
n皇后问题
n皇后问题是高斯提出的一个经典的问题，是指在一个n*n的棋盘上放置n各皇后，每行一个并使其不能相互攻击（同一行、同一列、同一斜线上的两个皇后都会相互攻击）。
因为同行（列）皇后会互相攻击且皇后数与行（列）数相等，所以每行（列）有且只有一个皇后，故皇后位置的行号和列号之间存在函数关系。
所以可以使用一维数组表示棋盘（下标从1开始），下标i表示行号，元素board[i]的值表示列号。
推得列冲突j==j0，主对角线冲突j-i == j0-i0, 次对角线冲突 i+j == i0+j0。
-
定义vaild(i,j)函数，对棋盘按行遍历检查能否在（i,j）位置上安放皇后（只检查不放置）。
-
定义常量vacant表示位置未被占用的值，该值很小防止使用0值让vaild函数误判。
-
定义i,j为当前将要试探的位置坐标，index为皇后的编号
算法流程：
将当前位置设定为入口位置，初始化棋盘
while ( i < = index ) {
while ( j <= index) {
if (当前位置不冲突) {
放置皇后
列号重置为1
跳出内层循环（j循环）
}
else {
若冲突则探索下一列 （j++）
}
}
若当前行没有放置位置，则说明上一行的放置有问题应进行回溯 {
若已经回溯到第1行
则说明已找到所有解，跳出循环终止搜索
否则
当前行号减1，清除上一行皇后位置重新搜索
}
若已扫描完最后一行
则找到一个解，将其打印；继续循环已搜索下一个解
}
C程序实现：
#include <stdio.h>
#include <stdlib.h>
int board[64]={0};
//使用一维数组存储棋盘，下标i表示皇后的行号，元素a[i]表示皇后的列号
//下标从1开始，a[i] == 0表示未放置皇后
//a[i]只有一个值避免了行冲突，每行或每列有且只有一个皇后每个a[i]都应有一个非0值。
int index=8;
//皇后数
#define vacan -1000 //定义表示位置未被占用的值，该值很小防止使用0值让vaild函数误判
int valid(int i, int j) {
int k;
for (k=1;k<index;k++) {
if ( board[k]==j || j-i == board[k]-k || i+j == k+board[k] ) {
//列冲突j==j0，主对角线冲突j-i == j0-i00, 次对角线冲突 i+j == i0+j0
return 0;
}
}
return 1;
}
int queens(void) {
int num=0; //记录解的个数
int i=1,j=1,iter; //记录当前行列号
for (iter=0;iter<=index;board[iter]=vacan,iter++); //初始化棋盘
while (i<=index) { //遍历行
while (j<=index) {
if (valid(i,j)) {
board[i]=j; //放置皇后
j=1; //重置列号
break;
}
else {
j++;
}
}
if (board[i] == vacan) {
//如果当前行没有放置位置，说明上一行的放置有问题应进行回溯
if (i==1) {
break; //如果回溯完第1行仍无解，说明已找到所有解
}
else {
i--; //回溯到上一行
j=board[i]+1; //因为1至board[i]均已扫描过，从下一列开始继续扫描。
board[i]=vacan; //清除上一行的皇后
continue;
}
}
if (i==index) { //如果已扫描到最后一行找到一个解，打印答案
printf("answer:%d
",++num);
for(iter=1;iter<=index;iter++) {
printf("[%d,%d]
",iter,board[iter]);
}
printf("
");
j=board[i]+1; //从最后一行下一列继续扫描
board[i]=vacan;
continue;
}
i++;
}
printf("num:%d
",num);
return num;
}
int main(void)
{
scanf("%d",&index);
queens();
return 0;
}
迷宫问题
给定二维数组表示迷宫（下标从0开始），0表示可以通行1表示不可通行。给出入口和出口的坐标，求出所有可能的简单路径（路径中没有循环，所有通道最多通过一次）。
-
路径的每一步包含行号、列号、下一方向3个要素，使用结构体表示一步（路径点）
-
使用0,1,2,3表示上左下右（顺时针方向旋转）四个方向，沿顺时针方向逐一试探
-
可通定义为该点为通道（对应元素为0）且不在路径点上，地图上的点有通道，障碍，路径点。压栈的同时将其标记为在路径上。
算法流程：
初始化迷宫
初始化栈，将入口位置压栈
while (栈不空) {
//判断是否到达出口
将当前试探位置及方向置为栈顶元素
若当前位置为出口
则打印路径退出
//沿当前方向试探下一位置
假设下一位置不可通（设定可通标记为假）
循环试探所有未试探方向 {
当前方向设为栈顶元素方向的下一方向，从该方向开始试探
若某一方向可通
设定可通标记为真，跳出循环
}
若下一位置可通（可通标记为真）
将该位置压栈，结束本次循环
否则
回溯到上一步，弹出栈顶
}
C程序实现：
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int x;
int y;
int dir; //the direction of the next step
} Step;
int board[10][10]= {
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,1,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
Step steps[1024];
int top=-1; //out of the end
int maze(int in_i,int in_j, int out_i, int out_j) {
int i=in_i, j=in_j,dire=0, acce; // direction , access
Step temp_step;
top=0;
steps[top].x=in_i;
steps[top].y=in_j;
steps[top].dir=0;
board[in_i][in_j]=-1;
while(steps[top].x != in_i || steps[top].y != in_j) { //栈顶位置不是出口
acce=0;
while (dire<4 && acce==0) {
dire++;
switch (dire) {
case 1: i=steps[top].x-1;
j=steps[top].y;
break;
case 2: i=steps[top].x;
j=steps[top].y+1;
break;
case 3: i=steps[top].x+1;
j=steps[top].y;
break;
case 4: i=steps[top].x;
j=steps[top].y-1;
break;
}
if (board[i][j] == 0) {
acce=1;
}
}
if (acce == 1) {
steps[top].dir = dire;
top++;
steps[top].dir = 0;
steps[top].x = i;
steps[top].y = j;
board[i][j]=-1;
}
else {
if (top < 0) {
return -1;
}
else {
board[steps[top].x][steps[top].y] = 0;
top--;
}
} //若栈空则找到全部解
}
return 0;
}
int main(void)
{
int t;
t=maze(1,1,8,8);
printf("%d
",t);
return 0;
}