八皇后问题汇总(C++版)

  • Post author:
  • Post category:其他




八皇后问题

在这里插入图片描述

八皇后问题(英文:Eight queens),是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题,是回溯算法的典型案例。

问题表述为:在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转,和对角线对称变换的摆法看成一类,共有42类。

放置第i个(行)皇后的算法为:

int search(int i){
	int j;
    for(j=1;j<=8;j++){
        if(本行本列允许放置皇后)
            放置第i个皇后;
            对放置皇后的位置进行标记;
            if(i==8)输出//已经放完8个皇后
            else search(i+1);//放置第i+1个皇后
        	释放标记,尝试下一个位置是否可行;
    }
}

【算法分析】

显然问题的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后。

可以从矩阵的特点上找到规律,如果在同一行,则行号相同;如果在同一列,则列号相同;

如果在/斜线上,则行列值之和相同,如果在\斜线上,则行列值之差相同。

考虑到每行有且只有一个皇后,设一维数组a[1…8]表示皇后的放置:第i行皇后放在第j列,用a[i]=j来表示,即下标是行数,内容是列数。例如:a[3]=5就表示第3个皇后在第3行第5列上。

判断皇后是否安全,即检查同一列、同一对角线是否已有皇后,建立标志数组b[1…8]控制同一列只能有一个皇后,若两皇后在同一对角线上,则其行列坐标之和或行列坐标之差相等,故亦可建立标志数组c[1…16],d[-7…7]控制同一对角线上只能有一个皇后。

【参考程序】

#include<bits/stdc++.h>
using namespace std;
bool d[17]={0},b[9]={0},c[17]={0};
int sum=0,a[9];
int search(int);
int print();
int main(){
	search(1);
	cout<<sum<<endl;
	return 0;
}
int search(int i){
	
	int j;
	for(j=1;j<=8;j++){
		if((!b[j])&&(!c[i+j])&&(!d[i-j+7])){//!b[j]--->表示不能在同一列
		//!c[i+j]--->表示不能在正对角线上
		//!d[i-j+7]--->表示不能在反对角线上
			a[i]=j;
			b[j]=1;
			c[i+j]=1;
			d[i-j+7]=1;
			if(i==8)print();
			else search(i+1);
			b[j]=0;
			c[i+j]=0;
			d[i-j+7]=0;
		}
	}
}
int print()
{	
	int i;
	sum++;
	for(int i=1;i<=8;i++)
		cout<<a[i]<<" ";
	cout<<endl;	
}




八皇后问题(来源:openjudge)

1700:八皇后问题

总时间限制: 10000ms 内存限制: 65536kB

描述

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

输入

无输入。

输出

按给定顺序和格式输出所有八皇后问题的解(见Sample Output)。

【算法分析】

本题依旧可以使用上面的代码去完成,但是会出现超时问题。此时需要注意:(1)把不需要返回值的函数重新定义为void;(2)使用printf编写输出。

这样时间上会加快不少。

scanf和printf比cin和cout要快很多,有时候会因为这个超时,所以虽然不知道为什么,但以后还是尽量用scanf和printf吧(还是要根据情况,如果数据比较大比较多就用省时的)(各有各的优势)

【参考程序】

深搜从0开始

参考地址

    #include<iostream>
    using namespace std;
    int cnt = 1;//方案计数器
    int chess[8][8];//棋盘情况
    bool judge(int row, int col);//判断某个位置是否可放
    void print();//输出函数
    void dfs(int row) {
    	if (row >= 8) {//深搜结束条件
    		print();
    		cnt++;
    		return;
    	}
    	for (int j = 0; j <= 7; j++) {
    		if (judge(row, j)) {
    			chess[row][j] = 1;
    			dfs(row + 1);//深搜
    			chess[row][j] = 0;//回溯,表示换个位置试试,之前的位置就当作没走咯
    		}
    	}
    }
    int main() {
    	dfs(0);
    	return 0;
    }
    bool judge(int row, int col) {
    	for (int i = 0; i <= 7; i++)//判断列
    		if (chess[i][col] == 1) return false;
    	for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {//判断左上对角线
    		if (chess[i][j] == 1) return false;
    	}
    	for (int i = row, j = col; i >= 0 && j <= 7; i--, j++) {//判断右上对角线
    		if (chess[i][j] == 1) return false;
    	}
    	return true;
    }
    void print() {
    	cout << "No. " << cnt << endl;
    	for (int j = 0; j <= 7; j++) {//!!!按列输出!!!
    		for (int i = 0; i <= 7; i++) {
    			if (chess[i][j] == 1) cout << "1" << " ";
    			else cout << "0" << " ";
    		}
    		cout << endl;
    	}
    }

深搜从1开始

    #include<bits/stdc++.h>
    using namespace std;
    bool a[9][9],b[9],c[17],d[17];
    int tot=0;
    void search(int);
    
    int main(){
    	search(1);
    	return 0;
    }
    void search(int i){//i代表皇后所在的行
    	int j;//代表皇后所在的列
    	for(j=1;j<=8;j++){//放置8个皇后
    		if((!b[j])&&(!c[i+j])&&(!d[j-i+7])){//!b[j]--->表示不能在同一列
    		//!c[i+j]--->表示不能在正对角线上
    		//!d[i-j+7]--->表示不能在反对角线上
    			a[i][j]=1;
    			b[j]=1;
    			c[i+j]=1;
    			d[j-i+7]=1;
    			if(i==8){
    				tot++;
    				cout<<"No. "<<tot<<endl;
    				for(int x=1;x<=8;x++){//按列输出皇后
    					for(int y=1;y<=8;y++)
    							cout<<a[y][x]<<" ";	
    					cout<<endl;
    				}
    			}
    			else search(i+1);
    			b[j]=0;//回溯
    			c[i+j]=0;
    			d[j-i+7]=0;
    			a[i][j]=0;
    		}
    	}
    	
    }

第三种解法(与上面第一个案例相似)

	#include<bits/stdc++.h>
    using namespace std;
    int a[9],b[9],c[17],d[17],tot=0;
    void search(int);
    int print();
    int main(){
    	search(1);
    	return 0;
    }
    void search(int i){
    	int j;
    	for(j=1;j<=8;j++){
    		if((!b[j])&&(!c[i+j])&&(!d[j-i+7])){//!b[j]--->表示不能在同一列
    		//!c[i+j]--->表示不能在正对角线上
    		//!d[i-j+7]--->表示不能在反对角线上
    			a[i]=j;
    			b[j]=1;
    			c[i+j]=1;
    			d[j-i+7]=1;
    			if(i==8){
    				tot++;
    				printf("No. %d\n",tot);
    				for(int x=1;x<=8;x++){//按列输出皇后
    					for(int y=1;y<=8;y++)
    							if(a[y]==x){
    							printf("1 ");
    							}	
    							else printf("0 ");
    					printf("\n");}
    			}
    			else search(i+1);
    			b[j]=0;
    			c[i+j]=0;
    			d[j-i+7]=0;
    		}
    	}
    }
    




八皇后(来源:openjudge)

1756:八皇后

总时间限制: 1000ms 内存限制: 65536kB

描述

会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。对于某个满足要求的8皇后的摆放方法,定义一个皇后串a与之对应,即a=b1b2…b8,其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解(即92个不同的皇后串)。给出一个数b,要求输出第b个串。串的比较是这样的:皇后串x置于皇后串y之前,当且仅当将x视为整数时比y小。

输入

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

输出

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

样例输入

2192

样例输出

1586372484136275

【算法分析】

提示:可以使用最上面案例的解法完成。

首先,如果每一次都去进行深搜的话一定会出现超时问题,所以最好的办法是先进行一次深搜,然后在深搜的过程中存储每一种方案,这样在进行输出是只需要从保存的方案中拿出来就可以了,时间复杂度为O(1)。

如果在保存过程中直接保存为八位数字,可以在输出时直接按位取数,这样就不再需要去进行八次循环输出了。

【参考程序】

    #include<bits/stdc++.h>
    using namespace std;
    bool d[17]={0},b[9]={0},c[17]={0};
    int sum=0,a[9],queen[95][9];
    void search(int);
    void print();
    int n,x;
    int main(){
    	cin>>n;
    	search(1);
    	for(int i=1;i<=n;i++){
    		cin>>x;
    		for(int j=1;j<=8;j++)
    			cout<<queen[x][j];
    		cout<<endl;
    	}
    	return 0;
    }
    void search(int i){//i代表皇后所在的行
    	int j;
    	for(j=1;j<=8;j++){
    		if((!b[j])&&(!c[i+j])&&(!d[i-j+7])){//!b[j]--->表示不能在同一列
    		//!c[i+j]--->表示不能在正对角线上
    		//!d[i-j+7]--->表示不能在反对角线上
    			a[i]=j;
    			b[j]=1;
    			c[i+j]=1;
    			d[i-j+7]=1;
    			if(i==8)print();
    			else search(i+1);
    			b[j]=0;
    			c[i+j]=0;
    			d[i-j+7]=0;
    		}
    	}
    	
    }
    
    	
    void print()
    {	
    	int i;
    	sum++;
    	for(int i=1;i<=8;i++)
    		queen[sum][i]=a[i];
    }	




P1219 [USACO1.5]八皇后 Checker Challenge(来源:洛古)


题目描述

一个如下的



6

×

6

6 \times 6






6




×








6





的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

上面的布局可以用序列



2

 

4

 

6

 

1

 

3

 

5

2\ 4\ 6\ 1\ 3\ 5






2




4




6




1




3




5





来描述,第



i

i






i





个数字表示在第



i

i






i





行的相应位置有一个棋子,如下:

行号



1

 

2

 

3

 

4

 

5

 

6

1\ 2\ 3\ 4\ 5\ 6






1




2




3




4




5




6




列号



2

 

4

 

6

 

1

 

3

 

5

2\ 4\ 6\ 1\ 3\ 5






2




4




6




1




3




5




这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。

并把它们以上面的序列方法输出,解按字典顺序排列。

请输出前



3

3






3





个解。最后一行是解的总个数。


输入格式

一行一个正整数



n

n






n





,表示棋盘是



n

×

n

n \times n






n




×








n





大小的。


输出格式

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。


样例 #1


样例输入 #1

6


样例输出 #1

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4


提示

【数据范围】

对于



100

%

100\%






100%





的数据,



6

n

13

6 \le n \le 13






6













n













13





题目翻译来自NOCOW。

USACO Training Section 1.5

【算法分析】

与之前的八皇后问题相似,把棋盘从



8

x

8

8×8






8


x


8





大小换成



n

x

n

nxn






n


x


n





大小,算法相同,需要注意的是

必须修改数组空间大小,适应题目要求的数据范围

【参考程序】

#include<bits/stdc++.h>
using namespace std;
int a[15],b[15],c[30],d[30],tot=0;
void search(int);int n;
int print();
int main(){
	
	cin>>n;
	search(1);
	cout<<tot;
	return 0;
}
void search(int i){
	int j;
	for(j=1;j<=n;j++){
		if((!b[j])&&(!c[i+j])&&(!d[j-i+7])){//!b[j]--->表示不能在同一列
		//!c[i+j]--->表示不能在正对角线上
		//!d[i-j+7]--->表示不能在反对角线上
			a[i]=j;
			b[j]=1;
			c[i+j]=1;
			d[j-i+7]=1;
			if(i==n){
				tot++;
				if(tot<=3){
					for(int x=1;x<=n;x++){//按列输出皇后
						printf("%d ",a[x]);
                    	}printf("\n");
				}
				}
			else search(i+1);
			b[j]=0;
			c[i+j]=0;
			d[j-i+7]=0;
		}
	}
}


未待完续



版权声明:本文为qq_43737458原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。