JakeLin

用户名：jake546

访问量：43190

签　名：

腾讯需要我！

等　　级
排　　名	40
经　　验	13199
参赛次数	3
文章发表	85
年　　龄	21
在职情况	学生
学　　校	华南农业大学
专　　业

　　自我简介：

幸福是奋斗出来的

TA的其他文章

JakeLin-1745题-继续畅通工程-题解(C++代码)-简单易懂
浏览：314

JakeLin-1729题-还是畅通工程-题解(C++代码)-简单易懂
浏览：292

JakeLin-2313题-[传智杯]软件工程实习-题解(C++代码)-结构体排序
浏览：289

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

JakeLin-1460题-2n皇后问题-题解(C/C++) - n皇后/2n皇后详解

　　作者: JakeLin　　　　发表时间：2020-02-28 16:30:32 浏览：810　|　评论：0　

原题链接：蓝桥杯基础练习VIP-2n皇后问题

##### 在我们学习2n皇后问题前，需要了解回溯法的一个经典题型：**八皇后问题**

------------

一、首先贴上**八皇后**问题：
> 给定一个8*8的棋盘。现在要向棋盘中放入8个皇后使任意的两个皇后都不在同一行、同一列或同一条对角线上问总共有多少种放法？

我们需要明确：
- 1、会有八个皇后被放入
- 2、每一行放一个（也仅有一个）
- 3、每一列也会有一个（也仅有一个）
- 4、如果用全排列或者八个for循环，结果多半是惨烈的

关键代码：
```cpp
int vis[10];   //vis[i]=1 表示第i【列】被访问过了，后面此列不被访问
int a[10];    //a[i]=j 表示第i个皇后（第i行）的位置为j->a[j]
void dfs(int step,int n) {   //安排第step个皇后（即第step【行】）
	if(step==n+1) {   //递归边界，表示n个皇后已经安排好了
		cnt++;
	} else {
		for(int i=1; i<=n; i++) {   //遍历i列
			if(vis[i]==0) {   //第i列必须是之前没访问过得一列
				bool tag = true;
				for(int j=1; j<step; j++) {   //遍历a数组1~step:查找与之前已经定好位的皇后是否冲突
					if(step-j == i-a[j] || step-j == a[j]-i) {
					//当前位置：（step,i）  之前位置（j,a[j]），若他们在对角线上，则斜率（step-j)/(i-a[j])为1或-1
						tag = false;
						break;
					}
				}
				if(tag) {	//  i列符合条件
					vis[i]=1;  // 访问
					a[step] = i;
					dfs(step+1,n);// 安排下一个皇后
					vis[i]=0;  // 回溯：恢复DFS之前的状态
				}
			}
		}
	}
}
```
近似思路题型应用变形，可见:point_right: [JakeLin-1540题-棋盘多项式-题解(C/C++描述)-详细解释](https://blog.dotcpp.com/a/67398 "JakeLin-1540题-棋盘多项式-题解(C/C++描述)-详细解释")

------------

二、迁移到**2n皇后**中问题：
> 不同之处为：每一行除了有一个黑皇后外，还会有一个白皇后。

所以我们按照上述做法查找一个位置给黑皇后之后，还需要在查找一次，给白皇后定位，**只有两位皇后都安排完毕了，才能进入下一行的定位**。
所以你会发现，不管是vis数组，还是皇后位置的数组，我们都需要准备两份

下面提供完整代码：

```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int cnt = 0;
int map[10][10]; //存储地图
int visb[10];   //visb[i]=1第i列已经有了黑皇后 
int visw[10];   //白皇后，同上 
int black[10];  //black[i]=j 表示第i个黑皇后（i行）在第j列
int white[10];  //白皇后的位置，同上
void dfs(int step,int n) {  //step代表第几行，要安排第几个皇后
	if(step==n+1) {
		cnt++;
	} else {
		for(int i=1; i<=n; i++) {  //第step行遍历i列（i->1-n）
			bool black_tag = true;
			if(visb[i]==0 && map[step][i]==1) {
				for(int j=1; j<step; j++) { //跟之前已经定好位的皇后做比较
					if(step-j == i-black[j] || step-j == black[j]-i) {  //斜对角方向 （step,i）和（j,a[j]）的斜率为1或-1
						black_tag = false;
						break;
					}
				}
				if(black_tag) {
					visb[i]=1;  //这一列有皇后了，后面一整列都不能访问
					black[step] = i;  //(step,i)->(step,a[step])
					for(int k=1; k<=n; k++) {
						if(k==i) continue;
						bool white_tag = true;
						if(visw[k]==0 && map[step][k]==1) {
							for(int j=1; j<step; j++) { //跟之前已经定好位的皇后做比较
								if(step-j == k-white[j] || step-j == white[j]-k) {  //斜对角方向 （step,k）和（j,a[j]）的斜率为1或-1
									white_tag = false;
									break;
								}
							}
							if(white_tag) {
								visw[k]=1;
								white[step] = k;
								dfs(step+1,n);   //搜索下一行（下一个皇后）
								visw[k]=0;
							}
						}
					}
					visb[i]=0;
				}
			}
		}
	}
}
int main() {
	int n;
	cin>>n;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			cin>>map[i][j];
		}
	}
	dfs(1,n);
	cout<<cnt;
	return 0;
}
```

###### 如果你觉得有、用，请为我点个评分吧嘻嘻嘻 :bowtie:

0.0分

19 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JakeLin

TA的其他文章

你可能喜欢

C二级辅导-温度转换（C语言代码）

整人!!

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

【回文数(二)】（C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

JakeLin-1460题-2n皇后问题-题解(C/C++) - n皇后/2n皇后详解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

DNA （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

The 3n + 1 problem （C语言代码）

妹子杀手的故事（C语言代码）

永远的丰碑（C语言代码）

C语言训练-自守数问题（C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

母牛的故事（C语言代码）

JakeLin

TA的其他文章

你可能喜欢

C二级辅导-温度转换 （C语言代码）

整人!!

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

【回文数(二)】 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

JakeLin-1460题-2n皇后问题-题解(C/C++) - n皇后/2n皇后详解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

DNA （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

The 3n + 1 problem （C语言代码）

妹子杀手的故事 （C语言代码）

永远的丰碑 （C语言代码）

C语言训练-自守数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

母牛的故事 （C语言代码）

C二级辅导-温度转换（C语言代码）

【回文数(二)】（C语言代码）

　　评论区

妹子杀手的故事（C语言代码）

永远的丰碑（C语言代码）

C语言训练-自守数问题（C语言代码）

母牛的故事（C语言代码）