C語言八皇后問題

相關推薦

C語言八皇后問題

　　八皇后問題是一個古老而著名的問題。該問題是19世紀著名的數學家高斯1850年提出：在一個8*8國際象棋盤上，有8個皇后，每個皇后占一格;要求皇后之間不會出現相互“攻擊”的現象，即不能有兩個皇后處在同一行、同一列或同一對角線上。問共有多少種不同的方法?

　　回溯算法也叫試探法，它是一種搜索問題的解的方法。冋溯算法的基本思想是在一個包含所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任意結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。

　　八皇后問題有很多中解法，其中使用回溯法進行求解是其中一種。而回溯發也是最直接的一種解法，也較容易理解。

　　八皇后問題的回溯法算法，可以采用一維數組來進行處理。數組的下標i表示棋盤上的第i列，a[i]的值表示皇后在第i列所放的位置。例如，a[1]=5，表示在棋盤的第例的第五行放一個皇后。程序中首先假定a[1]=1，表示第一個皇后放在棋盤的第一列的第一行的位置上，然后試探第二列中皇后可能的位置，找到合適的位置后，再處理后續的各列，這樣通過各列的反復試探，可以最終找出皇后的全部擺放方法。

　　八皇后問題可以使用回溯法進行求解，程序實現如下：

　　#include

　　#define Queens 8 //定義結果數組的大小，也就是皇后的數目

　　int a[Queens+1]; //八皇后問題的皇后所在的行列位置，從1幵始算起，所以加1

　　int main(){

　　int i, k, flag, not_finish=1, count=0;

　　//正在處理的元素下標，表示前i-1個元素已符合要求，正在處理第i個元素

　　i=1;

　　a[1]=1; //為數組的第一個元素賦初值

　　printf("The possible configuration of 8 queens are:\n");

　　while(not_finish){ //not_finish=l:處理尚未結束

　　while(not_finish && i<=Queens){ //處理尚未結束且還沒處理到第Queens個元素

　　for(flag=1,k=1; flag && k

　　if(a[k]==a[i])

　　flag=0;

　　for (k=1; flag&&k

　　if( (a[i]==a[k]-(k-i)) || (a[i]==a[k]+(k-i)) )

　　flag=0;

　　if(!flag){ //若存在矛盾不滿足要求，需要重新設置第i個元素

　　if(a[i]==a[i-1]){ //若a[i]的值已經經過一圈追上a[i-1]的值

　　i--; //退回一步，重新試探處理前一個元素

　　if(i>1 && a[i]==Queens)

　　a[i]=1; //當a[i]為Queens時將a[i]的值置1

　　else

　　if(i==1 && a[i]==Queens)

　　not_finish=0; //當第一位的值達到Queens時結束

　　else

　　a[i]++; //將a[il的值取下一個值

　　}else if(a[i] == Queens)

　　a[i]=1;

　　else

　　a[i]++; //將a[i]的值取下一個值

　　}else if(++i<=Queens)

　　if(a[i-1] == Queens )

　　a[i]=1; //若前一個元素的值為Queens則a[i]=l

　　else

　　a[i] = a[i-1]+1; //否則元素的值為前一個元素的下一個值

　　}

　　if(not_finish){

　　++count;

　　printf((count-1)%3 ? "\t[%2d]:" : "\n[%2d]:", count);

　　for(k=1; k<=Queens; k++) //輸出結果

　　printf(" %d", a[k]);

　　if(a[Queens-1]

　　a[Queens-1]++; //修改倒數第二位的值

　　else

　　a[Queens-1]=1;

　　i=Queens -1; //開始尋找下一個滿足條件的解

　　}

　　輸出結果：

　　The possible configuration of 8 queens are:

　　[ 1]: 1 5 8 6 3 7 2 4 [ 2]: 1 6 8 3 7 4 2 5 [ 3]: 1 7 4 6 8 2 5 3

　　[ 4]: 1 7 5 8 2 4 6 3 [ 5]: 2 4 6 8 3 1 7 5 [ 6]: 2 5 7 1 3 8 6 4

　　[ 7]: 2 5 7 4 1 8 6 3 [ 8]: 2 6 8 3 1 4 7 5 [ 9]: 2 6 1 7 4 8 3 5

　　[10]: 2 7 3 6 8 5 1 4 [11]: 2 7 5 8 1 4 6 3 [12]: 2 8 6 1 3 5 7 4

　　[13]: 3 5 7 1 4 2 8 6 [14]: 3 5 8 4 1 7 2 6 [15]: 3 5 2 8 1 7 4 6

　　[16]: 3 5 2 8 6 4 7 1 [17]: 3 6 8 1 4 7 5 2 [18]: 3 6 8 1 5 7 2 4

　　[19]: 3 6 8 2 4 1 7 5 [20]: 3 6 2 5 8 1 7 4 [21]: 3 6 2 7 1 4 8 5

　　[22]: 3 6 2 7 5 1 8 4 [23]: 3 6 4 1 8 5 7 2 [24]: 3 6 4 2 8 5 7 1

　　[25]: 3 7 2 8 5 1 4 6 [26]: 3 7 2 8 6 4 1 5 [27]: 3 8 4 7 1 6 2 5

　　[28]: 3 1 7 5 8 2 4 6 [29]: 4 6 8 2 7 1 3 5 [30]: 4 6 8 3 1 7 5 2

　　[31]: 4 6 1 5 2 8 3 7 [32]: 4 7 1 8 5 2 6 3 [33]: 4 7 3 8 2 5 1 6

　　[34]: 4 7 5 2 6 1 3 8 [35]: 4 7 5 3 1 6 8 2 [36]: 4 8 1 3 6 2 7 5

　　[37]: 4 8 1 5 7 2 6 3 [38]: 4 8 5 3 1 7 2 6 [39]: 4 1 5 8 2 7 3 6

　　[40]: 4 1 5 8 6 3 7 2 [41]: 4 2 5 8 6 1 3 7 [42]: 4 2 7 3 6 8 1 5

　　[43]: 4 2 7 3 6 8 5 1 [44]: 4 2 7 5 1 8 6 3 [45]: 4 2 8 5 7 1 3 6

　　[46]: 4 2 8 6 1 3 5 7 [47]: 5 7 1 3 8 6 4 2 [48]: 5 7 1 4 2 8 6 3

　　[49]: 5 7 2 4 8 1 3 6 [50]: 5 7 2 6 3 1 4 8 [51]: 5 7 2 6 3 1 8 4

　　[52]: 5 7 4 1 3 8 6 2 [53]: 5 8 4 1 3 6 2 7 [54]: 5 8 4 1 7 2 6 3

　　[55]: 5 1 4 6 8 2 7 3 [56]: 5 1 8 4 2 7 3 6 [57]: 5 1 8 6 3 7 2 4

　　[58]: 5 2 4 6 8 3 1 7 [59]: 5 2 4 7 3 8 6 1 [60]: 5 2 6 1 7 4 8 3

　　[61]: 5 2 8 1 4 7 3 6 [62]: 5 3 8 4 7 1 6 2 [63]: 5 3 1 6 8 2 4 7

　　[64]: 5 3 1 7 2 8 6 4 [65]: 6 8 2 4 1 7 5 3 [66]: 6 1 5 2 8 3 7 4

　　[67]: 6 2 7 1 3 5 8 4 [68]: 6 2 7 1 4 8 5 3 [69]: 6 3 5 7 1 4 2 8

　　[70]: 6 3 5 8 1 4 2 7 [71]: 6 3 7 2 4 8 1 5 [72]: 6 3 7 2 8 5 1 4

　　[73]: 6 3 7 4 1 8 2 5 [74]: 6 3 1 7 5 8 2 4 [75]: 6 3 1 8 4 2 7 5

　　[76]: 6 3 1 8 5 2 4 7 [77]: 6 4 7 1 3 5 2 8 [78]: 6 4 7 1 8 2 5 3

　　[79]: 6 4 1 5 8 2 7 3 [80]: 6 4 2 8 5 7 1 3 [81]: 7 1 3 8 6 4 2 5

　　[82]: 7 2 4 1 8 5 3 6 [83]: 7 2 6 3 1 4 8 5 [84]: 7 3 8 2 5 1 6 4

　　[85]: 7 3 1 6 8 5 2 4 [86]: 7 4 2 5 8 1 3 6 [87]: 7 4 2 8 6 1 3 5

　　[88]: 7 5 3 1 6 8 2 4 [89]: 8 2 4 1 7 5 3 6 [90]: 8 2 5 3 1 7 4 6

　　[91]: 8 3 1 6 2 5 7 4 [92]: 8 4 1 3 6 2 7 5

【C語言八皇后問題】相關文章：