回溯法又称“试探法”，按照优选条件去向前搜索，以达到目标。如果在搜索到某一步时，发现原先这样并不能满足条件，就回退一步重新选择，这种走不通就退回来再走的技术称为回溯法。做回溯法的题目时，有添加状态或元素就一定有与之对应的回退状态和元素。若是寻找成功，回退以查看有没有其他满足条件的解；如果寻找不成功，回退以查看其它情况。
回溯的关键不在于递归，而在于“状态”。在回溯算法向前的每一步，你都会去设置某个状态，而当向前走走不通的时候回退，此时需要把之前设置的状态撤销掉。
更抽象的，可以将回溯算法理解为深度遍历一颗N叉树，每个叶子结点都是一种方案的终态，而对某条路线的判断可能在访问到叶子结点之前就结束。
如三个数字1、2、3的全排列：
相比动态规划，回溯可以解决的问题更复杂，尤其是针对具有后效性的问题。
动态规划之所以无法处理有后效性问题，原因是其 dp(i)=F(dp(j)) 其中 0<=j<i 导致的，因为 i 通过 i-1 推导，如果 i-1 的某种选择会对 i 的选择产生影响，那么这个推导就是无效的。
而回溯，由于每条分支判断是相互独立的，互不影响，所以即便前面的选择具有后效性，这个后效性也可以在这条选择线路持续影响下去，而不影响其他分支。
回溯法是非线性解空间深度优先遍历时，不是一味的穷举，而是构造约束或限界条件（包含状态变量），当某一分支遇到约束或限界条件时，即回转到该分支的分叉口（状态变量恢复初始值），转而搜索另一条路径，直到求得一个满足目标条件或目标函数的解。或者，当满足目标条件或目标函数时，即回转到该分支的分叉口，转而搜索另一条路径，直到求得另一个解。
回溯法过程如下：
① 构造空间树；
② 进行遍历；
③ 如遇到边界或约束条件，即不再向下搜索，转回至分叉点，搜索另一个分支；
④ 达到目标条件，输出结果。
在一般情况下使用递归函数来实现回溯法比较简单，其中 i 为搜索的深度，框架如下：
void Backtracking()
{
If you are already at a solution, report success.
for ( every possible choice in the current position )
{
1 Make that choice and take one step along the path.
2 Use recursion to solve the problem from the new position.
3 If the recursive call succeeds, report the success to the next higher level.
4 If not, back out of the current choice to restore the previous state.
}
Report failure.
}
伪代码：
int a[n] = {0}; // 定义初始状态，通常为全局数组 ①
try(int i)
{
if(i>n)
//输出结果;
else
{
for(j =下界; j <= 上界; j=j+1) //枚举i所有可能的路径
{
if(fun(j)) //满足约束或限界条件，包含状态变量
{
a[i] = j; // 更新状态 ②
... //其他操作
try(i+1);
a[i] = 0; // 回溯前的清理工作（如a[i]置空值等，状态回退或回复）; ③
}
}
}
}
回溯法一般是在一个序列里做选择，序列的大小构成了树的宽度，递归的深度构成的树的深度。
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
for循环就是遍历序列，可以理解一个节点有多少个孩子，这个for循环就执行多少次。可以理解为横向的遍历。
backtrack就是自己调用自己，可以理解为纵向的遍历。
1 分书问题使用回溯法
有编号为0，1，2，3，4的5本书，准备分给5个人A，B，C，D，E，写一个程序，输出所有皆大欢喜的分书方案。
code demo:
include
using namespace std;
const int NUMS = 5;
int like[NUMS][NUMS]={ // 每个人的阅读兴趣用一个二维数组like描述
{0,0,1,1,0}, // like[i][j] = true // i喜欢书j
{1,1,0,0,1}, // Like[i][j] = false // i不喜欢书j
{0,1,1,0,1},
{0,0,0,1,0},
{0,1,0,0,1}};
int take[NUMS]={0}; // 记录每一本书的分配情况，定义状态, 全局变量
int solutions = 0; // 分书方案数
void trynext(int i);
void printScheme();
int main()
{
trynext(0);
getchar();
return 0;
}
void trynext(int i) //对第 i 个人进行分配
{
for(int j=0;j<NUMS;j++) // 枚举NUMS本书
if(like[i][j]&&take[j]==0)
{
take[j]=i+1; // 把第j本书分配给第i个人，状态更新
if(i==NUMS-1) // 第NUMS个人分配结束，也即所有的书分配完毕，可以将方案进行输出
printScheme();
else
trynext(i+1);//递归，对下一个人进行分配， dfs 下一层
take[j]=0; //回溯，寻找下一种方案，状态回退（take[j]是全局变量）
}
}
void printScheme()
{
solutions++;
cout<<"第"<<solutions<<"种分配方案"<<endl;
for(int k=0;k<NUMS;k++)
cout<<"第"<<k<<"本书分配给"<<(char)(take[k]+'A'-1)<<endl;
cout<<endl;
}
2 八皇后问题使用回溯法求解
八皇后问题显然具有 “强烈的” 后效性，因为皇后攻击范围是由其位置决定的，换而言之，一个皇后位置确定后，其他皇后的可能摆放位置会发生变化，因此只能用回溯算法。
在做回溯时，需要决定搜索合法、不合法以及结束时的动作。如果当前搜索节点合法，就可以进行下一层次的搜索。如果当前搜索节点不合法，则回退到上一个合法节点，继续进行下一步的搜索。如果搜索推进到最后一层且节点合法，则搜索到符合要求的结果，将该结果加入到结果列表。
用经典的8皇后问题对应举例，待搜索的行一共8行。如果当前节点x,y合法，就可以搜索x+1行，遍历所有8个y节点位置。如果当前搜索节点不合法，就要回退到x行的初始参数，搜索其余的y节点。如果搜索推进到第8行，且当前节点合法，则搜索到一个解，可将其加入结果列表。
code demo:
//代码效果参考：http://www.zidongmutanji.com/bxxx/414936.html
include
define n 4
int column[n2] = {0}; // 初始状态
int diag1[n2] = {0};
int diag2[n*2] = {0};
int count = 0;
void search(int y) {
if (y == n) {
count++;
return;
}
for (int x = 0; x < n; x++) {
if (column[x] || diag1[x+y] || diag2[x-y+n-1])
continue;
column[x] = diag1[x+y] = diag2[x-y+n-1] = 1; // 更新状态
search(y+1); // dfs 下一层
column[x] = diag1[x+y] = diag2[x-y+n-1] = 0; // 回退时的逆操作，下一轮循环x++，状态回退
}
return;
}
main()
{
search(0);
printf("%d\n",count);
getchar();
}
/
n=4, 2
n=8, 92
n=16, 14772512 /
code demo2:
include //回溯法（递归）
include //求绝对值函数需要引入该头文件
define M 105
using namespace std;
int n; // n表示n个皇后
int x[M]; // x[i]表示第i个皇后放置在第i行第x[i]列，表示解空间
int countn; // countn表示n皇后问题可行解的个数
bool Place(int t) // 判断第t个皇后能否放置在第x[t]个位置
{
bool flag=true;
for(int j=1;j<t;j++) // 判断该位置的皇后是否与前面t-1个已经放置的皇后冲突
{
if(x[t]==x[j]||t-j==fabs(x[t]-x[j]))// 判断列、对角线是否冲突
{
flag=false;
break;
}
}
return flag;
}
void Backtrack(int t) // t表示当前扩展结点在第t层
{
if(t>n) // 如果当前位置为n,则表示已经找到了问题的一个解
{
countn++;
for(int i=1; i<=n;i++) // 打印选择的路径
cout<<x[i]<<" ";
cout<<endl;
cout<<"----------"<<endl;
}
else
for(int i=1;i<=n;i++) //分别判断n个分支,特别注意i不要定义为全局变量,否则递归调用有问题
{
x[t]=i; // x[t]表示第t个皇后放置在第t行第x[t]=i列
if(Place(t)) // 如果不冲突的话进行下一行的搜索，否则考察下一个分支（兄弟结点）
Backtrack(t+1);
} // 如果冲突，则枚举下一种状态，并更新x[t]
}
int main()
{
cout<<"请输入皇后的个数 n:";
cin>>n;
countn=0;
Backtrack(1);
cout <<"答案的个数是："<<countn<< endl;
getchar();getchar();
return 0;
}
以上代码可以在以下站点做可视化运行过程跟踪：
https://pythontutor.com/render.html
3 迷宫maze问题
// 老鼠走迷宫是递回求解的基本题型，
// 我们在二维阵列中使用2表示迷宫墙壁，使用1来表示老鼠的行走路径，
// 试以程式求出由入口至出口的路径。
include
include
int visit(int,int);
int maze[7][7]={
{2,2,2,2,2,2,2},
{2,0,0,0,0,0,2},
{2,0,2,0,2,0,2},
{2,0,0,2,0,2,2},
{2,2,0,2,0,2,2},
{2,0,0,0,0,0,2},
{2,2,2,2,2,2,2}};
int startI=1, startJ=1; // 入口
int endI=5,endJ=5; // 出口
int success=0;
void showMaze()
{
int i,j;
printf("显示迷宫：\n");
for (i = 0; i < 7; i++)
{
for (j = 0; j < 7; j++)
if (maze[i][j] == 2)
printf("■");
else
printf(" ");
printf("\n");
}
}
// 老鼠的走法有上、左、下、右四个方向，
// 在每前进一格之后就选一个方向前进，无法前进时退回选择下一个可前进方向，
// 如此在阵列中依序测试四个方向，直到走到出口为止
int visit(int i,int j) {
maze[i][j] = 1;
if (i == endI && j == endJ)
success = 1; // 状态更新
if(success!=1 && maze[i] [j+1]==0) visit(i ,j+1);
if(success!=1 && maze[i+1][j] ==0) visit(i+1,j );
if(success!=1 && maze[i] [j-1]==0) visit(i ,j-1);
if(success!=1 && maze[i-1][j] ==0) visit(i-1,j );
if(success!=1)
maze[i][j]=0; // 回溯，状态回退到初始化
return success;
}
int main()
{
showMaze();
if(visit(startI,startJ)==0)
printf("\n没有找到出口！n");
else{
printf("\n显示路径：\n");
for(int i=0; i<7; i++)
{
for(int j=0; j<7; j++)
{
if(maze[i][j]==2)
printf("■");
else if(maze[i][j]==1)
printf("◇");
else
printf(" ");
}
printf("\n");
}
}
getchar();
return 0;
}
maze code demo2
include
include
define ROW 10
define COL 12
define EAST maze[x][y+1]
define WEST maze[x][y-1]
define SOUTH maze[x+1][y]
define NORTH maze[x-1][y]
//代码效果参考：http://www.zidongmutanji.com/bxxx/545210.html
define ExitX (ROW-2)
define ExitY (COL-2)
int maze[ROW][COL]={1,1,1,1,1,1,1,1,1,1,1,1, /声明迷宫数组/
1,2,0,0,1,1,0,1,1,1,1,1,
1,1,1,0,1,1,0,0,0,0,1,1,
1,1,1,0,1,1,0,1,1,0,1,1,
1,1,1,0,0,0,0,1,0,0,0,1,
1,1,1,0,1,1,0,1,1,0,1,1,
1,0,1,0,1,1,0,1,1,0,1,1,
1,0,1,0,1,1,0,0,1,0,1,1,
1,0,0,0,0,0,0,0,1,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1};
struct list
{
int x,y;
struct list next;
};
typedef struct list node;
typedef node link;
link push(link stack, int x, int y)
{
link newnode;
newnode = (link)malloc(sizeof(node));
if(!newnode)
{
printf("Error! 内存分配失败！\n");
return NULL;
}
newnode->x = x;
newnode->y = y;
newnode->next = stack;
stack = newnode;
return stack;
}
link pop(link stack, int x, int y)
{
link top;
if(stack!=NULL)
{
top = stack;
stack = stack->next;
x = top->x; y = top->y;
free(top);
return stack;
}
else
*x = -1;
return stack;
}
int chkExit(int x, int y, int ex, int ey)
{
if(x==ex && y == ey)
{
if(NORTH == 1 || SOUTH == 1 || WEST == 1 || EAST == 2)
return 1;
if(NORTH == 1 || SOUTH == 1 || WEST == 2 || EAST == 1)
return 1;
if(NORTH == 1 || SOUTH == 2 || WEST == 1 || EAST == 1)
return 1;
if(NORTH == 2 || SOUTH == 1 || WEST == 1 || EAST == 1)
return 1;
}
return 0;
}
void output()
{
for(int i=0; i<ROW; i++)
{
for(int j=0; j<COL; j++)
printf("%2d",maze[i][j]);
printf("\n");
}
printf("\n");
}
void mazeSolution()
{
int x,y; // 坐标
link path = NULL;
x=1;
y=1;
printf("迷宫模拟图（1表示墙，0表示通道）\n");
output();
//代码效果参考：http://www.zidongmutanji.com/zsjx/106531.html
while(x<=ExitX && y<=ExitY)
{
maze[x][y] = 6;
if(NORTH == 0)
{
x -= 1;
path = push(path,x,y);
}
else if(SOUTH == 0)
{
x += 1;
path = push(path,x,y);
}
else if(EAST == 0)
{
y += 1;
path = push(path,x,y);
}
else if(WEST == 0)
{
y -= 1;
path = push(path,x,y);
}
else if(chkExit(x,y,ExitX,ExitY)==1)
break;
else
{
maze[x][y] = 2;
path = pop(path,&x,&y);
}
}
printf("迷宫模拟图（6表示老鼠走过的路线）\n");
output();
}
int main()
{
mazeSolution();
while(1);
return 0;
}
/*
迷宫模拟图（1表示墙，0表示通道）
1 1 1 1 1 0 0 0 1 1 1 1
1 2 0 0 1 1 1 1 1 1 1 1
1 1 1 0 1 1 0 0 0 0 1 1
1 1 1 0 1 1 0 1 1 0 1 1
1 1 1 0 0 0 0 1 1 0 1 1
1 1 1 0 1 1 0 1 1 0 1 1
1 1 1 0 1 1 0 1 1 0 1 1
1 1 1 0 1 1 0 0 1 0 1 1
1 1 0 0 0 0 0 0 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1
迷宫模拟图（6表示老鼠走过的路线）
1 1 1 1 1 0 0 0 1 1 1 1
1 6 6 6 1 1 1 1 1 1 1 1
1 1 1 6 1 1 6 6 6 6 1 1
1 1 1 6 1 1 6 1 1 6 1 1
1 1 1 6 0 0 6 1 1 6 1 1
1 1 1 6 1 1 6 1 1 6 1 1
1 1 1 6 1 1 6 1 1 6 1 1
1 1 1 6 1 1 6 0 1 6 1 1
1 1 0 6 6 6 6 0 1 6 6 1
1 1 1 1 1 1 1 1 1 1 1 1
*/
