// 1140_八皇后.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。//題目1140：八皇后//時(shí)間限制：1 秒內(nèi)存限制：32 兆特殊判題：否提交：908解決：557//題目描述：//會(huì)下國(guó)際象棋的人都很清楚：皇后可以在橫、豎、斜線上不限步數(shù)地吃掉其他棋子。如何將8個(gè)皇后放在棋盤上（有8 * 8個(gè)方格），使它們誰(shuí)也不能被吃掉！這就是著名的八皇后問(wèn)題。 //對(duì)于某個(gè)滿足要求的8皇后的擺放方法，定義一個(gè)皇后串a(chǎn)與之對(duì)應(yīng)，即a=b1b2...b8，其中bi為相應(yīng)擺法中第i行皇后所處的列數(shù)。已經(jīng)知道8皇后問(wèn)題一共有92組解（即92個(gè)不同的皇后串）。//給出一個(gè)數(shù)b，要求輸出第b個(gè)串。串的比較是這樣的：皇后串x置于皇后串y之前，當(dāng)且僅當(dāng)將x視為整數(shù)時(shí)比y小。//輸入：//第1行是測(cè)試數(shù)據(jù)的組數(shù)n，后面跟著n行輸入。每組測(cè)試數(shù)據(jù)占1行，包括一個(gè)正整數(shù)b(1 <= b <= 92)//輸出：//輸出有n行，每行輸出對(duì)應(yīng)一個(gè)輸入。輸出應(yīng)是一個(gè)正整數(shù)，是對(duì)應(yīng)于b的皇后串。//樣例輸入：//2//1//92//樣例輸出：//15863724//84136275//來(lái)源：//2008年北京大學(xué)軟件所計(jì)算機(jī)研究生機(jī)試真題#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）這個(gè)點(diǎn)不能放皇后，或者是回溯回來(lái)，都執(zhí)行 }}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[][]數(shù)組如果用來(lái)表示哪些點(diǎn)可以放皇后的話，導(dǎo)致回溯的時(shí)候無(wú)法確認(rèn)哪些點(diǎn)要改回去，所以 visit數(shù)組還是應(yīng)該用來(lái)記錄哪些點(diǎn)已經(jīng)存放皇后 *///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;//}
