// 1140_八皇后.cpp : 定义控制台应用程序的入口点。//题目1140：八皇后//时间限制：1 秒内存限制：32 兆特殊判题：否提交：908解决：557//题目描述：//会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将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的皇后串。//样例输入：//2//1//92//样例输出：//15863724//84136275//来源：//2008年北京大学软件所计算机研究生机试真题#include "stdafx.h"#include "iostream"using namespace std;int result[100][10];int cnt;void eightQueen(int i,int j,int visit[9]){ if(i<=8 && j<=8){ int l; for(l =1;l<i;l++){ if(j==visit[l] || ((i-j)==(l-visit[l])) || ((i+j)==(l+visit[l]))) break; } if(l == i){ visit[i] = j; if(i == 8){ for(int k = 1;k<=8;k++) result[cnt][k] = visit[k]; cnt++; } else eightQueen(i+1,1,visit); } eightQueen(i,j+1,visit); //不管是（i,j）这个点不能放皇后，或者是回溯回来，都执行 }}int main(){ int n; int visit[9]; cnt = 1; eightQueen(1,1,visit); while(cin>>n){ while(n--){ int x; cin>>x; for(int k=1;k<=7;k++) cout<<result[x][k]; cout<<result[x][8]<<endl; } } return 0;}/*1.visit[][]数组如果用来表示哪些点可以放皇后的话，导致回溯的时候无法确认哪些点要改回去，所以 visit数组还是应该用来记录哪些点已经存放皇后 *///char result[93][9];//int cnt;////void eightQueen(int i,int j,int visit[9][9],int count,char temp[9]){// if (visit[i][j]){// count++;// if(count==8){// cnt++;// for(int k=0;k<7;k++)// result[cnt][k] = temp[k];// result[cnt][7] = j;// }// else{// temp[count-1] = j + '0';// for(int k = 1;k<=8;k++){// visit[k][j] = visit[i][k] = 0;// if(i+k<=8 && j-k>=1)// visit[i+k][j-k] = 0;// if(i+k<=8 && j+k<=8)// visit[i+k][j+k] = 0;// if(i-k>=1 && j-k>=1)// visit[i-k][j-k] = 0;// if(i-k>=1 && j+k<=8)// visit[i-k][j+k] = 0;// }// for(int k =1;k<=8;k++)// if(i+1<=8)// eightQueen(i+1,k,visit,count,temp);// count--;// for(int k = 1;k<=8;k++){// visit[i][k] = 1;// if(k>i) // visit[k][i] = 1;// if(i+k<=8 && j-k>=1)// visit[i+k][j-k] = 1;// if(i+k<=8 && j+k<=8)// visit[i+k][j+k] = 1;// if(i-k>=1 && j-k>=1)// visit[i-k][j-k] = 1;// if(i-k>=1 && j+k<=8)// visit[i-k][j+k] = 1;// }// if(j<7)// eightQueen(i,j+1,visit,count,temp);//// }// }// //}////int main()//{// int n;// int count = 0;// char temp[9];// int visit[9][9];// for(int i = 1;i<=8;i++)// for(int j= 1;j<=8;j++)// visit[i][j] = 1;// cnt = 0;// eightQueen(1,1,visit,count,temp);// while(cin>>n){// while(n--){// int x;// cin>>x;// cout<<result[x]<<endl;// }// }// return 0;//}
