// 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;//}
