#创作计划#八皇后:题意+思路+题解

*八皇后是一道深度优先搜索(DFS)题目,如果对于其概念并不清楚,可以去看:

Macw07的深度优先搜索 DFS : https://www.acgo.cn/discuss/study/19056

正题开始:

题目大意:
在8*8的棋盘放8个不在同一行,同一列,同意对角线的皇后,
每行输出一个长度为8的字符串：R1R2R3R4R5R6R7R8(0 <Ri <9，表示第i行，皇后所在的位置)

解题思路:（版本1，易理解写法）
1.首先,使用递归(深搜)进行查找,利用a数组存下列的位置,并在找齐8个皇后所在位置后输出:

dfs(1);

void dfs(int x){
	if(x==9){//这里的x之所以在9才停止,是因为x是从1开始的
		for(int i=1;i<=8;i++){
			cout<<a[i];
		}
		cout<<endl;
		return;
	}
}

2.在这样的循环里遍历位置

for(int i=1;i<=8;i++){
		for(int j=1;j<=8;j++){

		}
	}
//这种写法是错的

然后可以发现其实题目要求查找的是列,行就按1,2,3,4,5,6,7,8定就好,所以可以将行的遍历省去,将x当作行:

void dfs(int x){
	if(x==9){
		for(int i=1;i<=8;i++){
			cout<<a[i];
		}
		cout<<endl;
		return;
	}
	for(int i=1;i<=8;i++){//这里的i已经是列了

	}
}
//这种写法才是对的

3.检查当在前的位置摆放皇后是否合法,既同一行,同一列,同一对角线是否有其他皇后的存在?
(同一行不用检查,因为棋子的摆放位置就是按照x一行一行枚举下来的)

这里我们使用一个二维数组,记录棋子位置的摆放

bool b[10][10];

如果有一个棋子在第x行第i列摆放

b[x][i]=1;

将其标记

这样,我们就可以顺利的检查摆放位置是否合法了

浅提一下如何检查对角线:

首先,要知道对角线有两条,比如,我们在第一行第三列下放棋子,我们就需要检查

这两条对角线.
然后,因为我们遍历棋子位置是有序遍历的,所以如果要检查(3,3)这个点的两条对角线,只要检查(1,1),(2,2)两个位置和(1,5),(2,4)两个位置就可以了(后面的位置都没有遍历到,不需要检查)
4.如果摆放位置合法,记录下来

for(int i=1;i<=8;i++){
		if(check(x,i)){
			a[x]=i;
		} 
	}

伪代码:
*看伪代码并填充,可以帮助CSP-J/S初赛备考生

#include<bits/stdc++.h>
using namespace std;
int a[10];
bool b[10][10];
bool check(int x1,int y1){//检查函数
	for(int i=1;i<=8;i++){
		if(b[i][y1]){
			return 0;
		}
	}
	for(//检查对角线1){
		if(b[i][j]){
			return 0;
		}
	}
	for(//检查对角线2){
		if(b[i][j]){
			return 0;
		}
	}
	return 1;
}
void dfs(int x){
	if(x==  ){//截至条件
		for(int i=1;i<=8;i++){
			cout<<a[i];//输出
		}
		cout<<endl;
		return;
	}
	for(int i=1;i<=8;i++){
		if(check(x,i)){
			//如果满足条件,在a数组记录
			//标记
			//进入下一层
			//解除标记(回溯)
		} 
	}
}
int main(){
	dfs(1);
}

正解代码:

#include<bits/stdc++.h>
using namespace std;
int a[10];
bool b[10][10];
bool check(int x1,int y1){
	for(int i=1;i<=8;i++){
		if(b[i][y1]){
			return 0;
		}
	}
	for(int i=x1,j=y1;i>0&&j>0;i--,j--){
		if(b[i][j]){
			return 0;
		}
	}
	for(int i=x1,j=y1;i>0&&j<9;i--,j++){
		if(b[i][j]){
			return 0;
		}
	}
	return 1;
}
void dfs(int x){
	if(x==9){
		for(int i=1;i<=8;i++){
			cout<<a[i];
		}
		cout<<endl;
		return;
	}
	for(int i=1;i<=8;i++){
		if(check(x,i)){
			a[x]=i;
			b[x][i]=1;
			dfs(x+1);
			b[x][i]=0;
		} 
	}
}
int main(){
	dfs(1);
}

但是，以上的方法还是有些许繁琐，如何进行优化？
首先，能优化的地方肯定是判断check)部分
这里可以运用几个一维数组来记录列，对角线1，对角线2.
列的记录可以直接用li数组
那么对角线1和对角线2如何用一维数组记录？

这张图中，我们可以发现对角线1的行列相减相等，对角线2的行列相加相等。
所以，我们可以用一个数组d1来记录对角线1，一个数组d2来记录对角线2
当使用i行j列的格子摆放皇后时，我们将d1[i-j]和d2[i+j]标记
但是这里需要注意的是，i-j可能是负数，在数组中会越界。
所以可以标记d1[i-j+8]
*
注意：这里用8是因为此时最大的差不会超过8（到n*n也可以用n)
不用管是否符合原先的数值，因为这里不是要查特定的数值，只要不越界（大于等于0），能互相对应上，不重复（使用abs(绝对值)可能会重复)就可以了。

正解代码：

#include<bits/stdc++.h>
using namespace std;
int a[10];
int l[10];
int d1[10];
int d2[10];
void dfs(int x){
	if(x==9){
		for(int i=1;i<=8;i++)cout<<a[i];
		cout<<endl;
		return;
	}
	for(int i=1;i<=8;i++){
		if(l[i]||d1[i-x+8]||d2[i+x])continue;
		l[i]=1;
		d1[i-x+8]=1;
		d2[i+x]=1;
		a[x]=i;
		dfs(x+1);
		l[i]=0;
		d1[i-x+8]=0;
		d2[i+x]=0;
	}
}
int main(){
	dfs(1);
}