ybt1213 八皇后 & ybt1214 八皇后

ybt1213

【题目描述】

在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。

【无输入】

【输出】

按给定顺序和格式输出所有八皇后问题的解（见样例）。
【输出样例】

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
...以下省略

【题解】

每个皇后可以吃掉所在行，列，斜线共八个方向的棋子，国际象棋棋盘共有八行八列，有2*15个斜线因此八皇后问题的策略就是在每一行，每一列，有且只有一个皇后，并且任意两个皇后不在同一斜线。

观察样例，不难发现是以每一列皇后的所在行数升序排列的，（参考ybt1214，不过与其相反，ybt1214是以每一行的列数升序排列的）所以就可以这样分类讨论。

这时就可以确定方向，从左往右一列一列的枚举，在每一列分别枚举不同可行的皇后位置，每当假设一个位置有皇后，那就将她右边的控制点（控制点是什么？可以参考过河卒）打上标记，并且随着皇后的变化不断更新，这样就可以使以后的皇后有正确的可行位置。

这就是思路，算法还是要在代码中体现。

#include<iostream>
#include<cstdio>
using namespace std;
int num=0;
bool a[30][30]={0},b[30][30]={0};//a是方案棋盘，也就是存皇后的位置；b是控制棋盘，存当前能放或不能放皇后的位置
void print() {//打印方案，不用多说
	printf("No. %d\n",++num);//别忘了空格
	for(int i=1;i<=8;i++) { 
		for(int j=1;j<=8;j++)
			printf("%d ",int(a[i+10][j+10]));//加10的原因在后面第28行
		printf("\n");
	}
	return;
}
void dfs(int x,int y) {//x是当前已经决定的皇后的所在行,y是当前已经决定的皇后的所在列 
	a[x+10][y+10]=1;//首先使方案中本格有皇后
	if(y==8) {//列数到了最右边
		print();//可以输出
		a[x+10][y+10]=0;//由于已经输出方案，所以需要继续搜索，此皇后位置要空出来
		return; 
	}
	bool z[30][30]={0};//这是对控制棋盘起备份作用的备份棋盘，用于之后还原操作
	for(int k=1;y+k<=8;k++) {
		z[x+10][y+k+10]=b[x+10][y+k+10];//备份
		z[x+k+10][y+k+10]=b[x+k+10][y+k+10];
		z[x-k+10][y+k+10]=b[x-k+10][y+k+10];
		b[x+10][y+k+10]=1;//控制她右边可控制的格子
		b[x+k+10][y+k+10]=1;//由于这里＋k以及下面-k，所以数组可能超限（10*10），所以把数组改为（30*30），并将元素都向后移10位避免超限，这就是所有下标都加10的原因
		b[x-k+10][y+k+10]=1;
	}
	for(int k=1;k<=8;k++) {//开始枚举
		if(!(b[k+10][y+11])) {//格子未被控制
			dfs(k,y+1);//在（k,y+1）放置皇后
		}
	}
	for(int k=1;y+k<=8;k++) {//还原
		b[x+10][y+k+10]=z[x+10][y+k+10];
		b[x+k+10][y+k+10]=z[x+k+10][y+k+10];
		b[x-k+10][y+k+10]=z[x-k+10][y+k+10];
	}
	a[x+10][y+10]=0;//和19行类似，再把这个皇后拿走
	return;
}
int main() {
	for(int l=1;l<=8;l++)
		dfs(l,1);//枚举第一个皇后的位置
	return 0; 
}

做这道题时，我遇到几个问题：

1.玄学的t变量

在一开始，本来想打个标记，判断无解跳出，在现在的第30行的后面建了一个t变量。最后，程序调好了，t也没用了，但是当我删掉t了以后，程序无输出，调试发现根本没有执行17行的if语句。然后又加上t，还是不行。吓得我赶紧撤销，撤回t还在的情况，唯一的区别是之前的t有赋值0。当t有赋值时，程序正常输出，无论赋值多少。

最后只能带着t提交，结果re，发现是爆数组了，因为皇后的斜着走操作有可能爆10*10的数组，最后数组扩大才解决。

2.格式出错

终于调好了程序的我再次提交，结果格式错误，仔细查看样例发现“No.”里的“.”后面是有空格的，又贡献了一次的KD

ybt1214

【题目描述】

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 × 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。

给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

【输入】

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1≤b≤92)。

【输出】

输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。

【输入样例】

2 1 92

【输出样例】

15863724
84136275

【题解】

在上一题的基础上把打印方案改为存储方案即可

注意！由于方案的对称性，所以虽然优先级不同，但还是可以通用之前的方案顺序。（务必先看ybt1213）

#include<iostream>
#include<cstdio>
using namespace std;
int num=0,c,n,ans[100][30];
bool a[30][30]={0},b[30][30]={0};
void record() {
	++num;
	for(int i=1;i<=8;i++) { 
		for(int j=1;j<=8;j++)
			if(a[i+10][j+10])
				ans[num][j+10]=i;
	}
	return;
}
void dfs(int x,int y) {
	a[x+10][y+10]=1;
	if(y==8) { 
		record();
		a[x+10][y+10]=0;
		return; 
	}
	bool z[30][30]={0};
	for(int k=1;y+k<=8;k++) {
		z[x+10][y+k+10]=b[x+10][y+k+10];
		z[x+k+10][y+k+10]=b[x+k+10][y+k+10];
		z[x-k+10][y+k+10]=b[x-k+10][y+k+10];
		b[x+10][y+k+10]=1;
		b[x+k+10][y+k+10]=1;
		b[x-k+10][y+k+10]=1;
	}
	for(int k=1;k<=8;k++) {
		if(!(b[k+10][y+11])) {
			dfs(k,y+1);
		}
	}
	for(int k=1;y+k<=8;k++) {
		b[x+10][y+k+10]=z[x+10][y+k+10];
		b[x+k+10][y+k+10]=z[x+k+10][y+k+10];
		b[x-k+10][y+k+10]=z[x-k+10][y+k+10];
	}
	a[x+10][y+10]=0;
	return;
}
int main() {
	cin>>n;
	for(int l=1;l<=8;l++)
		dfs(l,1);
	for(int m=1;m<=n;m++) {
		cin>>c;
		for(int o=1;o<=8;o++)
			cout<<ans[c][o+10];
		cout<<endl; 
	}
	return 0; 
}