用经典的8皇后问题对应举例，待搜索的行一共8行。如果当前节点x,y合法，就可以搜索x+1行，遍历所有8个y节点位置。如果当前搜索节点不合法，就要回退到x行的初始参数，搜索其余的y节点。如果搜索推进到第8行，且当前节点合法，则搜索到一个解，可将其加入结果列表。

code demo:

#include 
#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
",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;jn)                        // 如果当前位置为n,则表示已经找到了问题的一个解
    {
        countn++;
        for(int i=1; i<=n;i++)    // 打印选择的路径
          cout<>n;
    countn=0;
    Backtrack(1);
    cout <<"答案的个数是："<

以上代码可以在以下站点做可视化运行过程跟踪：

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("显示迷宫：
");
    for (i = 0; i < 7; i++)
    {
        for (j = 0; j < 7; j++)
            if (maze[i][j] == 2)
                printf(" ");
            else
                printf("  ");
            printf("
");
    }
}
// 老鼠的走法有上、左、下、右四个方向，
// 在每前进一格之后就选一个方向前进，无法前进时退回选择下一个可前进方向，
// 如此在阵列中依序测试四个方向，直到走到出口为止
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");
    else{
        printf("
显示路径：
");
        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("
");
        }
    }
    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]

#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! 内存分配失败！
");
        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

ref

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

-End-