八皇后问题汇总（C++版）

八皇后问题

八皇后问题

在这里插入图片描述

八皇后问题（英文：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;
    		}
    	}
    }

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将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的皇后串。

样例输入

样例输出

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 \times 6

$6 \times 6$

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

上面的布局可以用序列

2\ 4\ 6\ 1\ 3\ 5

$246135$

来描述，第

i

$i$

个数字表示在第

i

$i$

行的相应位置有一个棋子，如下：

行号

1\ 2\ 3\ 4\ 5\ 6

$123456$

列号

2\ 4\ 6\ 1\ 3\ 5

$246135$

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

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

请输出前

3

$3$

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

输入格式

一行一个正整数

n

$n$

，表示棋盘是

n \times n

$n \times n$

大小的。

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

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

提示

【数据范围】

对于

100\%

$100%$

的数据，

≤

6 \le n \le 13

$6 \leq n \leq 13$

。

题目翻译来自NOCOW。

USACO Training Section 1.5

【算法分析】

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

8×8

$8 x 8$

大小换成

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;
		}
	}
}

~~未待完续~~

原文链接：https://blog.csdn.net/qq_43737458/article/details/128973039

八皇后问题汇总（C++版）

八皇后问题

你可能也喜欢