北大题库2.5-1700:八皇后问题

发布时间:2024年01月06日

八皇后问题

也是很经典的递归和搜索题。
先来看一下题吧。

1700:八皇后问题
总时间限制: 10000ms 内存限制: 65536kB
描述
在国际象棋棋盘上放置八个皇后,要求每两个皇后之间不能直接吃掉对方。
输入
无输入。
输出
按给定顺序和格式输出所有八皇后问题的解(见Sample Output)。
样例输入
样例输出
No. 1
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
No. 2
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0
No. 3
1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0
No. 4
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
No. 5
0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
No. 6
0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0
No. 7
0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0
No. 8
0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
No. 9
0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0
…以下省略

思路:可以每一个位置都遍历一遍。(但是可能会超时)。所以我们可以把每一列看做一个整体,(因为一个皇后可以吃一列),这样我们的递归就只有八层,不会超时。
递归思路:每一列就是递归的每一层,每次进行标记+填充+搜索下一列+删除标记,到边界在输出就行了。
递归边界:因为是八皇后,所以到我们遍历完第八列时,即n(列)>8时,就可以输出了。

	if(n>8)//填充完成!输出。
	{
		cout<<"No. "<<++sum<<endl;//优美的输出。
		for(int i=0;i<8;i++)
		{
			for(int j=1;j<=8;j++)
			{
				cout<<a[i][j]<<" ";
			}
			cout<<endl;
		}
	}

接下来就是最关键的地方,我们该如何标记,填充呢。

:因为我们是遍历列,所以递归每一层往下,就相当于被标记,不存在重复问题。

:行应该很简单,定义一个f[10]数组,每次如果填充,就给这一行打上标记,表示已被填充。

斜行和斜列:斜行和斜列可以看一下这个图。
在这里插入图片描述

不难发现,每一斜行和斜列的和和差总是相等的。所以判断在哪一斜行和斜列,就可以用行坐标+列坐标和行坐标-列坐标+8(+8是为了避免行坐标小于列坐标)来判断。这样我们也可以用f1[10]和f2[10]两个数组来标记。

标记完,就是填充了,填充完表示该列已完成工作,我们就可以遍历下一列了,即递归下一层。

填好一个八皇后后,别忘了删除标记和填充内容!

核心代码

for(int i=0;i<8;i++)//每列中的八个位置,也就是八行。
	{
		if(f[i]==0&&f1[i-n+8]==0&&f2[i+n]==0) //判断是否被标记过。(i即是每一行,n就是递归的参数,即每一列)
		{
			f[i]=1;//快乐标记!
			f1[i-n+8]=1;
			f2[i+n]=1;
			a[i][n]=1;//标记完成,填充!
			bhh(n+1);//填充完成!搜索下一列!
			f[i]=0;//别忘了收尾!
			f1[i-n+8]=0;//清除标记!
			f2[i+n]=0;
			a[i][n]=0;//清除填充内容!
		}
	}

这就是递归的主体了。剩下我们把传参代码写一下就行了。

int main()
{
	bhh(1);//从第一列开始搜索!
    return 0;
}

好了,这个问题就解决了。
整体代码如下:

#include<bits/stdc++.h>
using namespace std;
int a[1010][10000],m,n,sum,f[100],f1[1000],f2[1000];
void bhh(int n)
{
	if(n>8)
	{
		cout<<"No. "<<++sum<<endl;
		for(int i=0;i<8;i++)
		{
			for(int j=1;j<=8;j++)
			{
				cout<<a[i][j]<<" ";
			}
			cout<<endl; 
		}
	}
	for(int i=0;i<8;i++)
	{
		if(f[i]==0&&f1[i-n+8]==0&&f2[i+n]==0)
		{
			f[i]=1;
			f1[i-n+8]=1;
			f2[i+n]=1;
			a[i][n]=1;
			bhh(n+1);
			f[i]=0;
			f1[i-n+8]=0;
			f2[i+n]=0;
			a[i][n]=0;
		}
	}
	
}
int main()
{
	bhh(1);
    return 0;
}

在这里插入图片描述

拓展:
这是先遍历列的写法。同样的我们也可以把行、斜行和斜列看作为整体去先遍历搜索。

同时我们可以将边界,循环的范围8改成m,这就可以随心所欲地构建皇后,不仅仅是八皇后,还有四皇后、五皇后、甚至是十皇后和n皇后。

文章来源:https://blog.csdn.net/zsb532712/article/details/135418717
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。