八皇后问题汇总（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;
}
}
}
八皇后（来源：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;
}
}
}
未待完续