八皇后问题，秒懂递归回溯（有图详解|c语言）

这篇具有很好参考价值的文章主要介绍了八皇后问题，秒懂递归回溯（有图详解|c语言）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

👸🏻前言

👸🏻题目介绍

👸🏻引入：

👸🏻解决思路：

👸🏻理论存在，实践开始！

👸🏻难点1：如何表示对角线被占领？

👸🏻难点2：如何用递归的方法来放皇后？

👸🏻难点3：如何实现回溯？

👸🏻难点4：如何实现皇后位置的输出？

👸🏻全部代码如下：

👸🏻总结：

Love is worth years.❤热爱可抵岁月漫长。

前言

各位和我一样的刚学完递归的小白们，是不是突然遇见了一个大BOSS，八皇后👸🏻问题！！把自信的说着“老子递归学好了！”的你一棒子打回了出生点，就像你刚玩只狼遇到的那个大胖子，刚玩原神遇到的雪山。今天，我就和大家一起学习一下这个著名的八皇后👸🏻问题。

题目介绍

八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法并输出每一种摆法。

八皇后问题c语言,c语言,c语言,算法,学习

升华：我在做这个东西的时候本来想用人脑将他们摆进去，发现太！麻！烦！可能这就是计算机存在的意义吧！

引入：

不知道大家有没有在前面学习递推的时候学过马拦过河卒的问题没看过的可以点这，这个问题和那个问题都是一个棋类的问题，他们也有相同之处，都是需要用一个数组来表示这个地方有没有被占领，象棋的那个题是马占领的地方需要标记，而这个题是皇后占领的每一行每一列每一个对角线都需要标记。所以我们可以采用一些个数组来表示这个地方被皇后占领了。当然这个题还用到了一个重要的算法就是递归算法和回溯的思想。

解决思路：

1.首先定义三个数组分别表示列被占领，左对角线被占领，和右对角线被占领。因为我们一行一行的放进去所以不用考虑行的问题。👸🏻

2.利用递归算法在没有被占领的地方一行一行的放入我们的皇后。👸🏻

3.利用递归和回溯算法一行一行的放入皇后。👸🏻

理论存在，实践开始！

难点1：如何表示对角线被占领？

用数组来表示列被占领很简单，只要让皇后所在的那一列的数组的值都等于0，就可以解决这个问题，但如何用数组来表达对角线呢？？你知道吧！你数一数，这一共有多少个对角线？一共有15条对角线，所以我们可以定义两个数组d1和d2来用来表示两个方向的对角线。如果被占领就是0没有被占领就是1

定义代码如下：

int d1[15]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};//定义上对角线
int d2[15]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1} ;//定义下对角线

如何在摆放的时候来确定哪一行哪一列呢？这样定义十五行太好定义了但是想要表示就难了，我们来研究一下这个东西。看下图，如这个第五列第三行的这个女皇，这个皇后占领了这两个对角线，如何来表示上对角线（皇后👸🏻的左上和右下从右上脚开始1、2、3、4、5...）？d1[n-col+7]=0;（col为女皇所在的列）也就是让行减去列再加上7就是表示的上对角线的个数。八皇后问题c语言,c语言,c语言,算法,学习

有小朋友要问了：你咋知道的？？？给你看一个上对角线的图！！

用行-列得到的图是这样的（我的那个棋盘没有第零行，大家可以看成有第零行的和列的，这个图太难改了你懂我的意思吧）：

八皇后问题c语言,c语言,c语言,算法,学习

而把这个数加7也就是行-列+7，是这样的：八皇后问题c语言,c语言,c语言,算法,学习

这样我们不就可以用行标和列标来表示他所在的上对角线了嘛，神器吧！！

希望各位xdm都把这个背过说实话我要是自己推我也推不出来这个玩意！！

下对角线：用行加列就会神奇的发现变成了下面这个样子：八皇后问题c语言,c语言,c语言,算法,学习

好了xdm现在让我们大声背三遍：

上对角线：行-列+7！！行-列+7！！行-列+7！！

下对角线：行+列！！行+列！！行+列！！

好了记住了吧！！！不要忘记了！像对待女朋友的生日一样对待这几个字！！！

这样我们就可以用：d1[n-col+7]，d2[n+col]来读取皇后的对角线的占领情况了！

这个难点解决了，我们来进入下一个难点递归。

难点2：如何用递归的方法来放皇后？

1.皇后的放置问题：place[8]={0};来表示皇后的位置的话，用table[8][8]={0};来表示一个8*8的大棋盘用一个for循环来访问棋盘的每一行，如果这个位置可以放（那几个约束条件都是1没有被占领的话）我们就可以让这一行的皇后的位置棋盘上放上皇后即place[n]=col;，表示皇后在此列👸🏻（一会打印的时候可以用的到）然后让皇后的列和那两个对角线为0，表示占领! flag[col]=0; d1[n-col+7]=0;d2[n+col]=0;

2.皇后的递归调用问题：

我们想要一行一行的摆放皇后，然后一列一列的尝试对不对

用col来表示列的话，用一个循环： for (col=0;col<8;col++)来访问每一列！

放置皇后用数组place[n]=col;（n表示行）来表示这个列，我皇后👸🏻占了！！！

flag[col]=0; d1[n-col+7]=0;d2[n+col]=0;//将该皇后所在的行、列、对角线设置为被占领

这样我们皇后在一行的放置问题解决了！，那么如何访问每一行呢？

这时候我们就需要用到神奇的递归神器！

如果queen(n+1);发现，老资👸🏻没座位了！他就会对queen(n);说：“姐姐，姐姐你能不能去下一个座位让妹妹我坐下呀”如果queen(n)；发现她如果向下面去她也没座位了她会向queen(n-1)说：....直到这8个皇后全坐下了，他们不吵架了，我们才能把这个棋盘输出出来！！！

这不就是老和尚给小和尚讲故事的递归嘛，而这个故事的大结局是皇后全都坐下！

我们如果这个行数小于七行（初始行为0你要是初始行为一可以加一）我们就可以继续向下摆放，对不对，就继续使用递归，来摆这个棋盘的下一行。

if(n<7) {queen(n+1);}//当行数小于7时；递归调用下一行。

如果我们的皇后把这次棋盘的摆好了我们就可以把这个棋盘输出出来了！

else{print();}（这个函数我们下面讲）//调用输出函数，

请大家看代码：

int queen(int n )//定义递归回溯函数
{
	int col;
	for (col=0;col<8;col++)
	{
		if (flag[col]&&d1[n-col+7]&&d2[n+col])//判断皇后是否冲突
		{
			place[n]=col;//放置皇后
			flag[col]=0;
			d1[n-col+7]=0;
            d2[n+col]=0;//将该皇后所在的行、列、对角线设置为被占领
			if(n<7)	{queen(n+1);}//当行数小于7时；递归调用下一行
		else{print();}//调用输出函数
			flag[col]=1;//回溯
			d1[n-col+7]=1;
			d2[n+col]=1;
		}
	}
	return count;
}

输出了一个棋盘还不够，我们要输出所有的棋盘，怎么办呢？？这时候我们就要请我们的回溯算法登场了！

难点3：如何实现回溯？

因为我们用的是递归算法如果这一行输出不了我们就把责任退回给上一行，直到我们找到了一个棋盘上面正好能够放着这八个皇后的时候我们就把他打印出来了。逻辑是不是这样的

那么如果我们在循环的最后加上flag[col]=1; d1[n-col+7]=1; d2[n+col]=1;是不是就是把这个占领的皇后踢出去了，然后再把这个皇后放在下一列来看看后面的那些皇后能不能成功摆放？

什么时候会触发这个回溯算法呢？？

答案是：当上面的递归算法全执行完了一次，并且输出了一个棋盘后，我们就可以让她执行第二次了！！

我们来继续讲一个故事：最后那个👸🏻在自己家里呆够了，老娘不想呆了，她又和楼上说，我要去下一个地方玩玩，你们看看怎么给我协调一下，原来我的位置就空出来了。楼上想；你去下面我去哪啊！于是他只好和楼上说，楼下和他说过的话。

这就是flag[col]=1; d1[n-col+7]=1; d2[n+col]=1;老娘不想待了，全给我搬家！

运行完这个以后呢，for循环中的col就进入下一列了，他这样一进不要紧，又触发了递归算法，一层一层的倒换，来满足需求。

当这个皇后全尝试了一遍其他能尝试的地方，就安稳了。

这样讲应该能讲明白为什么使用这个回溯算法，以及回溯算法为什么在if里面了吧如果不在if里面，这个回溯算法就没有意义了。

            flag[col]=1;//回溯
			d1[n-col+7]=1;
			d2[n+col]=1;

难点4：如何实现皇后位置的输出？

这个时候我们可以直接用一个输出函数来输出

这部分简单直接上代码：

void print()//定义输出函数
{
	int i,j;
    count++;//每调用一次输出函数number自加一次，记录摆放方法个数
	printf("No.%2d\n",count);
	int table[8][8]={0};//设置一个8*8的棋盘
	for (i=0;i<8;i++)
	{
		table[i][place[i]]=1;//将每一行皇后所在位置赋值为1
	}
	for (i=0;i<8;i++)
	{
		for (j=0;j<8;j++)
		{
	printf("%d|",table[i][j]);
		}printf("\n");
	}
}

这样我们就能输出这些傲娇的皇后们了！！

全部代码如下：

#include<stdio.h>
int place[8]={0};//皇后位置
int flag[8]={1,1,1,1,1,1,1,1};//定义列
int d1[15]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};//定义上对角线（共有15个对角线,
//因此定义一个长度为15的数组，初值为1代表该对角线没有被皇后占领，
//若被皇后占领则赋值为0
int d2[15]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1} ;//定义下对角线
int count=0;//记录输出次数
void print()//定义输出函数
{
	int i,j;
    count++;//每调用一次输出函数number自加一次，记录摆放方法个数
	printf("No.%2d\n",count);
	int table[8][8]={0};//设置一个8*8的棋盘
	for (i=0;i<8;i++)
	{
		table[i][place[i]]=1;//将每一行皇后所在位置赋值为1
	}
	for (i=0;i<8;i++)
	{
		for (j=0;j<8;j++)
		{
	printf("%d|",table[i][j]);
		}printf("\n");
	}
}
int queen(int n)//定义递归回溯函数
{
	int col;
	for (col=0;col<8;col++)
	{
		if (flag[col]&&d1[n-col+7]&&d2[n+col])//判断皇后是否冲突
		{
			place[n]=col;//放置皇后
			flag[col]=0;
			d1[n-col+7]=0;
            d2[n+col]=0;//将该皇后所在的行、列、对角线设置为被占领
			if(n<7)	{queen(n+1);}//当行数小于7时；递归调用下一行
            else{print();}//调用输出函数
            flag[col]=1;//回溯
			d1[n-col+7]=1;
			d2[n+col]=1;
		}
	}
	return count;
}
int main()
{
count=queen(0);//从第0行开始摆放皇后
printf("共有%d种方法",count);//输出摆放皇后的方法个数
	return 0;}

运行结果部分如下：

八皇后问题c语言,c语言,c语言,算法,学习