本文共 2743 字，大约阅读时间需要 9 分钟。
在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。
无输入。
按给定顺序和格式输出所有八皇后问题的解（见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 ...以下省略
此题可使用函数递归调用的方法求解。
八皇后，八行八列，两个皇后之间不能在同一行，不能在同一列，不能在同一对角线。
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 15 0 1 0 0 0 0 0 06 0 1 0 1 0 0 0 07 0 0 0 0 0 1 0 08 0 0 1 0 0 0 0 0#include#include #include #include #define N 100using 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<
转载地址：http://wvzci.baihongyu.com/