2698:八皇后问题
在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。
Input
无输入。
Output
按给定顺序和格式输出所有八皇后问题的解（见Sample Output）。
Sample Input
Sample Output
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
No. 3
1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0
No. 4
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
No. 5
0 0 0 0 0 1 0 0
1 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 0 0 0 0 1
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
No. 6
0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 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 0 0 0 1 0
0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0
No. 7
0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0
No. 8
0 0 1 0 0 0 0 0
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
No. 9
0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 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 0 0 1 0
0 0 1 0 0 0 0 0
...以下省略
Hint
此题可使用函数递归调用的方法求解。
题意：
八皇后，八行八列，两个皇后之间不能在同一行，不能在同一列，不能在同一对角线。
1 2 3 4 5 6 7 8
1 1 0 0 0 0 0 0 0 可以看到a[1,1]点和a[2,2]点在同一对角线，a[3,5]点和a[6,2]点在同一对角线。
2 0 1 0 0 0 0 1 0 而他们的关系都是|2-1|=|2-1| |2-5|=|6-3| 即列的差的绝对值=行的差的绝对值。
3 0 0 0 0 1 0 0 0 不能在同一行和不能在同一列就比较好判断了
4 0 0 0 0 0 0 0 1
5 0 1 0 0 0 0 0 0
6 0 1 0 1 0 0 0 0
7 0 0 0 0 0 1 0 0
8 0 0 1 0 0 0 0 0
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 100
using namespace std;
int a[N][N],b[N]; //数组a存放八皇后的所有可能 数组b存放一遍搜索的八皇后的可能
int vis[N]; //标记列上是否已经有皇后
int s; //八皇后的所有可能
int check(int step)
{ //如果两列上皇后的行的差=列的差 或者 两列上皇后的行相同，说明放的位置错误 for(int i=1;i<=step-1;i++)if((abs(b[i]-b[step])==abs(i-step))) return 0;return 1;
}
void dfs(int step) //搜索行
{if(step==8+1) {s++;for(int i=1; i<=8; i++)a[s][i]=b[i];return;} for(int i=1; i<=8; i++) //循环判断每一列上是否可以放皇后{if(vis[i]==0) //说明此列上未放过皇后{b[step]=i; //将step行的i列上放上皇后if(check(step)) //检查是否符合八皇后{vis[i]=1; dfs(step+1); vis[i]=0; }}}
}
int main()
{dfs(1);for(int t=1; t<=s; t++){printf("No. %d\n",t);for(int i=1; i<=8; i++){for(int j=1; j<=8; j++){if(a[t][j]==i) cout<<"1 ";else cout<<"0 ";}cout<<endl;}}return 0;
}