/*n皇后问题*/ #include <iostream> #include<algorithm> #include<queue> #include<stack> #include<cmath> #include<string.h> #include<stdio.h> #include<stdlib.h> using namespace std; #define maxn 1000 int n,tot,col[maxn],vis[3][maxn]; void search(int cur) { int i,j; if(cur==n) { tot++; printf("----解%d:---- ",tot); for(i=0; i<n; i++) { printf("x = %d y = %d ",i,col[i]); } printf(" "); }//递归边界。只要走到这所以皇后必然不冲突 else for(i=0; i<n; i++) { //优化前： /*int ok=1; col[cur]=i;//尝试把第cur行的皇后放在第i列 for(j=0; j<cur; j++)//检查是否和前面的皇后冲突 if(col[cur]==col[j]||cur-col[cur]==j-col[j]||cur+col[cur]==j+col[j]) { ok=0; break; } if(ok) search(cur+1);//如果合法，则继续递归*/ //优化后:(回溯法) if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n]) //利用二位数组直接判断 { col[cur]=i;//如果不打印解,整个col数组都可以省略 vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=1;//修改全局变量 search(cur+1); vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=0;//切记一定要改回来 } } } int main() { while(scanf("%d",&n)==1) { tot=0; memset(vis,0,sizeof(vis)); search(0); printf("共有解 %d 个 ",tot); } return 0; } /* 4 ----解1:---- x = 0 y = 1 x = 1 y = 3 x = 2 y = 0 x = 3 y = 2 ----解2:---- x = 0 y = 2 x = 1 y = 0 x = 2 y = 3 x = 3 y = 1 共有解 2 个 8 ---省略---- . . . ----解64:---- x = 0 y = 4 x = 1 y = 7 x = 2 y = 3 x = 3 y = 0 x = 4 y = 6 x = 5 y = 1 x = 6 y = 5 x = 7 y = 2 ----解65:---- x = 0 y = 5 x = 1 y = 0 x = 2 y = 4 x = 3 y = 1 x = 4 y = 7 x = 5 y = 2 x = 6 y = 6 x = 7 y = 3 ----解66:---- x = 0 y = 5 x = 1 y = 1 x = 2 y = 6 x = 3 y = 0 x = 4 y = 2 x = 5 y = 4 x = 6 y = 7 x = 7 y = 3 ----解67:---- x = 0 y = 5 x = 1 y = 1 x = 2 y = 6 x = 3 y = 0 x = 4 y = 3 x = 5 y = 7 x = 6 y = 4 x = 7 y = 2 ----解68:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 0 x = 3 y = 6 x = 4 y = 4 x = 5 y = 7 x = 6 y = 1 x = 7 y = 3 ----解69:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 0 x = 3 y = 7 x = 4 y = 3 x = 5 y = 1 x = 6 y = 6 x = 7 y = 4 ----解70:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 0 x = 3 y = 7 x = 4 y = 4 x = 5 y = 1 x = 6 y = 3 x = 7 y = 6 ----解71:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 4 x = 3 y = 6 x = 4 y = 0 x = 5 y = 3 x = 6 y = 1 x = 7 y = 7 ----解72:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 4 x = 3 y = 7 x = 4 y = 0 x = 5 y = 3 x = 6 y = 1 x = 7 y = 6 ----解73:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 6 x = 3 y = 1 x = 4 y = 3 x = 5 y = 7 x = 6 y = 0 x = 7 y = 4 ----解74:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 6 x = 3 y = 1 x = 4 y = 7 x = 5 y = 4 x = 6 y = 0 x = 7 y = 3 ----解75:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 6 x = 3 y = 3 x = 4 y = 0 x = 5 y = 7 x = 6 y = 1 x = 7 y = 4 ----解76:---- x = 0 y = 5 x = 1 y = 3 x = 2 y = 0 x = 3 y = 4 x = 4 y = 7 x = 5 y = 1 x = 6 y = 6 x = 7 y = 2 ----解77:---- x = 0 y = 5 x = 1 y = 3 x = 2 y = 1 x = 3 y = 7 x = 4 y = 4 x = 5 y = 6 x = 6 y = 0 x = 7 y = 2 ----解78:---- x = 0 y = 5 x = 1 y = 3 x = 2 y = 6 x = 3 y = 0 x = 4 y = 2 x = 5 y = 4 x = 6 y = 1 x = 7 y = 7 ----解79:---- x = 0 y = 5 x = 1 y = 3 x = 2 y = 6 x = 3 y = 0 x = 4 y = 7 x = 5 y = 1 x = 6 y = 4 x = 7 y = 2 ----解80:---- x = 0 y = 5 x = 1 y = 7 x = 2 y = 1 x = 3 y = 3 x = 4 y = 0 x = 5 y = 6 x = 6 y = 4 x = 7 y = 2 ----解81:---- x = 0 y = 6 x = 1 y = 0 x = 2 y = 2 x = 3 y = 7 x = 4 y = 5 x = 5 y = 3 x = 6 y = 1 x = 7 y = 4 ----解82:---- x = 0 y = 6 x = 1 y = 1 x = 2 y = 3 x = 3 y = 0 x = 4 y = 7 x = 5 y = 4 x = 6 y = 2 x = 7 y = 5 ----解83:---- x = 0 y = 6 x = 1 y = 1 x = 2 y = 5 x = 3 y = 2 x = 4 y = 0 x = 5 y = 3 x = 6 y = 7 x = 7 y = 4 ----解84:---- x = 0 y = 6 x = 1 y = 2 x = 2 y = 0 x = 3 y = 5 x = 4 y = 7 x = 5 y = 4 x = 6 y = 1 x = 7 y = 3 ----解85:---- x = 0 y = 6 x = 1 y = 2 x = 2 y = 7 x = 3 y = 1 x = 4 y = 4 x = 5 y = 0 x = 6 y = 5 x = 7 y = 3 ----解86:---- x = 0 y = 6 x = 1 y = 3 x = 2 y = 1 x = 3 y = 4 x = 4 y = 7 x = 5 y = 0 x = 6 y = 2 x = 7 y = 5 ----解87:---- x = 0 y = 6 x = 1 y = 3 x = 2 y = 1 x = 3 y = 7 x = 4 y = 5 x = 5 y = 0 x = 6 y = 2 x = 7 y = 4 ----解88:---- x = 0 y = 6 x = 1 y = 4 x = 2 y = 2 x = 3 y = 0 x = 4 y = 5 x = 5 y = 7 x = 6 y = 1 x = 7 y = 3 ----解89:---- x = 0 y = 7 x = 1 y = 1 x = 2 y = 3 x = 3 y = 0 x = 4 y = 6 x = 5 y = 4 x = 6 y = 2 x = 7 y = 5 ----解90:---- x = 0 y = 7 x = 1 y = 1 x = 2 y = 4 x = 3 y = 2 x = 4 y = 0 x = 5 y = 6 x = 6 y = 3 x = 7 y = 5 ----解91:---- x = 0 y = 7 x = 1 y = 2 x = 2 y = 0 x = 3 y = 5 x = 4 y = 1 x = 5 y = 4 x = 6 y = 6 x = 7 y = 3 ----解92:---- x = 0 y = 7 x = 1 y = 3 x = 2 y = 0 x = 3 y = 2 x = 4 y = 5 x = 5 y = 1 x = 6 y = 6 x = 7 y = 4 共有解 92 个 x = 1 y = 7 x = 2 y = 3 x = 3 y = 0 x = 4 y = 2 x = 5 y = 5 x = 6 y = 1 x = 7 y = 6 ----解64:---- x = 0 y = 4 x = 1 y = 7 x = 2 y = 3 x = 3 y = 0 x = 4 y = 6 x = 5 y = 1 x = 6 y = 5 x = 7 y = 2 ----解65:---- x = 0 y = 5 x = 1 y = 0 x = 2 y = 4 x = 3 y = 1 x = 4 y = 7 x = 5 y = 2 x = 6 y = 6 x = 7 y = 3 ----解66:---- x = 0 y = 5 x = 1 y = 1 x = 2 y = 6 x = 3 y = 0 x = 4 y = 2 x = 5 y = 4 x = 6 y = 7 x = 7 y = 3 ----解67:---- x = 0 y = 5 x = 1 y = 1 x = 2 y = 6 x = 3 y = 0 x = 4 y = 3 x = 5 y = 7 x = 6 y = 4 x = 7 y = 2 ----解68:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 0 x = 3 y = 6 x = 4 y = 4 x = 5 y = 7 x = 6 y = 1 x = 7 y = 3 ----解69:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 0 x = 3 y = 7 x = 4 y = 3 x = 5 y = 1 x = 6 y = 6 x = 7 y = 4 ----解70:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 0 x = 3 y = 7 x = 4 y = 4 x = 5 y = 1 x = 6 y = 3 x = 7 y = 6 ----解71:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 4 x = 3 y = 6 x = 4 y = 0 x = 5 y = 3 x = 6 y = 1 x = 7 y = 7 ----解72:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 4 x = 3 y = 7 x = 4 y = 0 x = 5 y = 3 x = 6 y = 1 x = 7 y = 6 ----解73:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 6 x = 3 y = 1 x = 4 y = 3 x = 5 y = 7 x = 6 y = 0 x = 7 y = 4 ----解74:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 6 x = 3 y = 1 x = 4 y = 7 x = 5 y = 4 x = 6 y = 0 x = 7 y = 3 ----解75:---- x = 0 y = 5 x = 1 y = 2 x = 2 y = 6 x = 3 y = 3 x = 4 y = 0 x = 5 y = 7 x = 6 y = 1 x = 7 y = 4 ----解76:---- x = 0 y = 5 x = 1 y = 3 x = 2 y = 0 x = 3 y = 4 x = 4 y = 7 x = 5 y = 1 x = 6 y = 6 x = 7 y = 2 ----解77:---- x = 0 y = 5 x = 1 y = 3 x = 2 y = 1 x = 3 y = 7 x = 4 y = 4 x = 5 y = 6 x = 6 y = 0 x = 7 y = 2 ----解78:---- x = 0 y = 5 x = 1 y = 3 x = 2 y = 6 x = 3 y = 0 x = 4 y = 2 x = 5 y = 4 x = 6 y = 1 x = 7 y = 7 ----解79:---- x = 0 y = 5 x = 1 y = 3 x = 2 y = 6 x = 3 y = 0 x = 4 y = 7 x = 5 y = 1 x = 6 y = 4 x = 7 y = 2 ----解80:---- x = 0 y = 5 x = 1 y = 7 x = 2 y = 1 x = 3 y = 3 x = 4 y = 0 x = 5 y = 6 x = 6 y = 4 x = 7 y = 2 ----解81:---- x = 0 y = 6 x = 1 y = 0 x = 2 y = 2 x = 3 y = 7 x = 4 y = 5 x = 5 y = 3 x = 6 y = 1 x = 7 y = 4 ----解82:---- x = 0 y = 6 x = 1 y = 1 x = 2 y = 3 x = 3 y = 0 x = 4 y = 7 x = 5 y = 4 x = 6 y = 2 x = 7 y = 5 ----解83:---- x = 0 y = 6 x = 1 y = 1 x = 2 y = 5 x = 3 y = 2 x = 4 y = 0 x = 5 y = 3 x = 6 y = 7 x = 7 y = 4 ----解84:---- x = 0 y = 6 x = 1 y = 2 x = 2 y = 0 x = 3 y = 5 x = 4 y = 7 x = 5 y = 4 x = 6 y = 1 x = 7 y = 3 ----解85:---- x = 0 y = 6 x = 1 y = 2 x = 2 y = 7 x = 3 y = 1 x = 4 y = 4 x = 5 y = 0 x = 6 y = 5 x = 7 y = 3 ----解86:---- x = 0 y = 6 x = 1 y = 3 x = 2 y = 1 x = 3 y = 4 x = 4 y = 7 x = 5 y = 0 x = 6 y = 2 x = 7 y = 5 ----解87:---- x = 0 y = 6 x = 1 y = 3 x = 2 y = 1 x = 3 y = 7 x = 4 y = 5 x = 5 y = 0 x = 6 y = 2 x = 7 y = 4 ----解88:---- x = 0 y = 6 x = 1 y = 4 x = 2 y = 2 x = 3 y = 0 x = 4 y = 5 x = 5 y = 7 x = 6 y = 1 x = 7 y = 3 ----解89:---- x = 0 y = 7 x = 1 y = 1 x = 2 y = 3 x = 3 y = 0 x = 4 y = 6 x = 5 y = 4 x = 6 y = 2 x = 7 y = 5 ----解90:---- x = 0 y = 7 x = 1 y = 1 x = 2 y = 4 x = 3 y = 2 x = 4 y = 0 x = 5 y = 6 x = 6 y = 3 x = 7 y = 5 ----解91:---- x = 0 y = 7 x = 1 y = 2 x = 2 y = 0 x = 3 y = 5 x = 4 y = 1 x = 5 y = 4 x = 6 y = 6 x = 7 y = 3 ----解92:---- x = 0 y = 7 x = 1 y = 3 x = 2 y = 0 x = 3 y = 2 x = 4 y = 5 x = 5 y = 1 x = 6 y = 6 x = 7 y = 4 共有解 92 个 */