#include<iostream> using namespace std; #define N 8 //N代表皇后數 void queen() { int Count=0; //計算總共的解的數量 int column[N+1]; //column[m]=n表示第m行，第n行放置了皇后,這里下表并從0開始 int row[N+1]; //row[m]=1表示第m行沒有皇后，=0表示有皇后 int b[2*N+1]; //b[m]=1表示第m條主對角線沒有皇后， int c[2*N+1]; //c[m]=1表示第m條次對角線沒有皇后，=0表示有皇后 int numQueen=1; //計數已經放置的皇后數目，當numQueen=N時候則表示已經完成探測 int good=1; //good=1表示沒有發生沖突,good=0表示發生沖突 //初始化這些標記 for(int j=0;j<N+1;++j) { row[j]=1; } for(int j=0;j<2*N+1;++j) { b[j]=c[j]=1; } column[1]=1; column[0]=0; //初始化第一行第一列，第二行第二列放置皇后 do { //沒有發生沖突，則繼續向下探測，增加皇后或者判斷當前是否是解 if(good) { //當前皇后數是解，打印，繼續向下探測 if(numQueen==N) { Count++; cout<<"找到解"<<endl; for(int j=1;j<N+1;++j) { cout<<j<<"列"<<column[j]<<"行"<<endl; } //最后一個棋子向下移動,移動到本列最后一個 while(column[numQueen]==N) { numQueen--; //皇后數減1，即列數減1，回溯 //回溯后將該列以及該列最后一行狀態位修改 //第numQueen列column[numQueen]行處狀態位置修改 row[column[numQueen]]=1; b[numQueen+column[numQueen]]=1; c[N+numQueen-column[numQueen]]=1; } column[numQueen]++; //回溯至上一行，向上一行的下一列繼續探測 } //當前不是解，那么繼續向下探測 else { //改變該位置對應標志 row[column[numQueen]]=0; b[numQueen+column[numQueen]]=0; c[N+numQueen-column[numQueen]]=0; //本次位置沒有發生沖突，也不是正確解，那么就應該向下探測下一列的第一行 column[++numQueen]=1; } } //如果當前發生了沖突，就在本列繼續向下，如果到了本列最后一行，則回溯到上一列 else { while(column[numQueen]==N) //到了本列最后一行，還是沖突，那么回溯到上一列 { numQueen--; row[column[numQueen]]=1; b[numQueen+column[numQueen]]=1; c[N+numQueen-column[numQueen]]=1; } column[numQueen]++; //發生沖突了，又沒有到本列的最后一行，那么在本列繼續向下一行探測 } //檢測放置了這個位置后是否沖突 good=row[column[numQueen]]&b[numQueen+column[numQueen]]&c[N+numQueen-column[numQueen]]; }while(numQueen); cout<<N<<"皇后總共找到解："<<Count<<"個"<<endl; } void main() { queen(); system("pause"); }

這種非遞歸方法還是比較容易理解的

?

另外還有遞歸方法，先來看一下遞歸算法的偽代碼

void trial(int row)

{

???? //遞歸時候，我們從第0行開始，然后每次遞歸時候，都向下一行，一直到棋盤的最后一行

???? //這時候就表示已經是正確的解了，所有進入該函數首先判斷是否是正確的解

???? if(row>N)

??? {

???????? //輸出此時的棋盤

??? }

????else

??? {

??????? for(int i=0;i<N;++i)

??????? {?

???????????? //不是解，這時候需要在本行的每一列開始試探放旗子，如果可以的話繼續向下遞歸

???????????? #修改記錄沖突的數組

???????????? ?if(放在這個位置不會沖突)

???????????? {

???????????????????? trial(row+1);

???????????? }

???????????? 放在這里沖突，那么修改回記錄的數組，繼續下一列

??????? }

???? }

}

?

下面給出遞歸的

void EightQueen (int row) { if(row>N) { PrintMap(); //打印棋盤 } else { int column; for (column = 0; column < N; ++column) { A[row]= column; //代表第row行的第column列放皇后 if (IsCorrect (row, column)) //判斷在第row行的第column列放皇后是否可行 { EightQueen (row + 1); } //將標記數組修改回原來 } } }

查看源代碼示例

查看源代碼示例

轉載于:https://blog.51cto.com/seanyxie/1375902

總結

以上是生活随笔為你收集整理的八皇后问题（回溯法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。