回溯法又称“试探法”，按照优选条件去向前搜索，以达到目标。如果在搜索到某一步时，发现原先这样并不能满足条件，就回退一步重新选择，这种走不通就退回来再走的技术称为回溯法。做回溯法的题目时，有添加状态或元素就一定有与之对应的回退状态和元素。若是寻找成功，回退以查看有没有其他满足条件的解；如果寻找不成功，回退以查看其它情况。

回溯的关键不在于递归，而在于“状态”。在回溯算法向前的每一步，你都会去设置某个状态，而当向前走走不通的时候回退，此时需要把之前设置的状态撤销掉。

更抽象的，可以将回溯算法理解为深度遍历一颗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 <iostream>
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:

#include <stdio.h>
#define n 4
int column[n*2] = {0}; // 初始状态
int  diag1[n*2] = {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 <iostream>         //回溯法（递归）
#include<cmath>             //求绝对值函数需要引入该头文件
#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<stdio.h>
#include<stdlib.h>
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 <stdio.h>
#include <stdlib.h>

#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]

#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();

    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
*/

ref

https://zhuanlan.zhihu.com/p/384626884

-End-