題目
會下國際象棋的人都很清楚：皇后可以在橫、豎、斜線上不限步數(shù)地吃掉其他棋子。如何將8個皇后放在棋盤上（有8 * 8個方格），使它們誰也不能被吃掉！這就是著名的八皇后問題。
對于某個滿足要求的8皇后的擺放方法，定義一個皇后串a(chǎn)與之對應(yīng)，即a=b1b2…b8，其中bi為相應(yīng)擺法中第i行皇后所處的列數(shù)。已經(jīng)知道8皇后問題一共有92組解（即92個不同的皇后串）。
給出一個數(shù)b，要求輸出第b個串。串的比較是這樣的：皇后串x置于皇后串y之前，當(dāng)且僅當(dāng)將x視為整數(shù)時比y小。
輸入
第1行是測試數(shù)據(jù)的組數(shù)n，后面跟著n行輸入。每組測試數(shù)據(jù)占1行，包括一個正整數(shù)b(1 <= b <= 92)
輸出
輸出有n行，每行輸出對應(yīng)一個輸入。輸出應(yīng)是一個正整數(shù)，是對應(yīng)于b的皇后串。
樣例輸入
2
1
92
樣例輸出
15863724
84136275

//錯誤代碼，按題目要求a=b1b2...b8，其中bi為相應(yīng)擺法中第i行皇后所處的列數(shù)。 #include <iostream> using namespace std; //用來存儲方案 ,下標都是從1開始 int a[9][9]; int visRow[9]; //行 int visLeftIncline[17];//左斜線 使用的時候 row+column int visRightIncline[16]; //右斜線，使用的時候row-column+8 int ansCount=0; int b[93][10];void print(){++ansCount;for(int i=1;i<=8;i++){for(int j=1;j<=8;j++){if(a[i][j]==1){b[ansCount][i]=j;break; } }}} void search(int column){if(column>8){//if(ansCount>=5) return;print();//cout<< ansCount<<endl;}else{for(int row=1;row<=8;row++){if(!visRow[row]&&!visLeftIncline[row+column]&&!visRightIncline[row-column+8]){visRow[row]=1;visLeftIncline[row+column]=1;visRightIncline[row-column+8]=1;a[row][column]=1;search(column+1);//找下一列//回溯 visRow[row]=0;visLeftIncline[row+column]=0;visRightIncline[row-column+8]=0;a[row][column]=0; }}} }int main(){search(1);int n,aww;cin>>n;for(int i=0;i<n;++i){cin>>aww;for(int j=1;j<=8;++j){cout<<b[aww][j];}cout<<endl;} return 0; } //ac代碼： //明明是從第一列到第八列的行數(shù)的組合，題目絕對有問題 #include <iostream> using namespace std; //用來存儲方案 ,下標都是從1開始 int a[93][9]; int visRow[9]; //行 int visLeftIncline[17];//左斜線 使用的時候 row+column int visRightIncline[16]; //右斜線，使用的時候row-column+8 int ansCount=1;void init(){}void print(){int case1;cin>>case1;int detailCase;while(case1--){cin>>detailCase;for(int i=1;i<=8;i++){cout<<a[detailCase][i];}cout<<endl;}} void search(int column){if(column>8){++ansCount; //因為是樹形結(jié)構(gòu)，所以下面的解要用到前面的解//因為是直接從中間開始，所以前面的值直接用 ansCount-1填//for(int i=1;i<=8;i++){a[ansCount][i]=a[ansCount-1][i];}}else{for(int row=1;row<=8;row++){if(!visRow[row]&&!visLeftIncline[row+column]&&!visRightIncline[row-column+8]){visRow[row]=1;visLeftIncline[row+column]=1;visRightIncline[row-column+8]=1;a[ansCount][column]=row;//記錄這一列是在第幾行search(column+1);//找下一列//回溯 visRow[row]=0;visLeftIncline[row+column]=0;visRightIncline[row-column+8]=0;}}} }int main(){init(); search(1);print();return 0; }

總結(jié)

以上是生活随笔為你收集整理的（回溯2）8皇后的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。