/* 著名的八皇后问题 DFS+回溯 由于每一行有且只有一个皇后 所以递归对每一行进行遍历即可 很多地方都不完善 稍后贴出改进版代码 */ #define LOCAL #include<iostream> #include<cstring> #include<string> using namespace std; int map[10][10],queen[100],nqueen=0; bool legal(int x,int y)//判断当前位置是否可放 { int i,j; for(i=1;i<=8;i++) { if(i!=x&&map[i][y]==1) return false; } for(i=x,j=y;i>=1&&j>=1;i--,j--) { if(i!=x&&map[i][j]==1) return false; } for(i=x,j=y;i>=1&&j<=8;i--,j++) { if(i!=x&&map[i][j]==1) return false; } for(i=x,j=y;i<=8&&j>=1;i++,j--) { if(i!=x&&map[i][j]==1) return false; } for(i=x,j=y;i<=8&&j<=8;i++,j++) { if(i!=x&&map[i][j]==1) return false; } return true; } void getqueen()//存储得到的八皇后序列 { int sum=0,i,j,t=1; for(i=8;i>=1;i--) { j=1; while(map[i][j]!=1) j++; sum+=j*t; t*=10; } queen[nqueen++]=sum; } void DFS(int m)//深搜遍历m代表搜索深度也代表棋盘行数 { if(m>8) return;//放置完毕返回 int i; for(i=1;i<=8;i++)//对第m行的各个格子进行遍历 { if(!map[m][i]&&legal(m,i))//如果当前位置可放置一个皇后 { map[m][i]=1;//标记为已放置 DFS(m+1);//搜索下一行 if(m==8)//如果八个皇后都已经放置完毕 getqueen();//保存皇后序列 map[m][i]=0;//反标记当前位置 } } } int main() { #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int ncase,n; memset(map,0,sizeof(map)); DFS(1);//从第一行开始放置 cin>>ncase; while(ncase--) { cin>>n; cout<<queen[n-1]<<endl; } return 0; }