[ 資料結構 小學堂 ] 堆疊 : 堆疊應用 (八皇后問題)

前言 : 
西洋棋的王后可以縱向、橫向、斜向的任意移動，但如何在一個8乘8個正方形格子的棋盤上放置 8 個王后，使任一個王后不被其他的王后吃掉呢？這個問題是Franz Nauck於1850年最先提出的。數學家高斯(Gauss)曾猜測此問題有96個解，但後來經過嚴格證明，實際上只有92個解，但是其中有些解經過旋轉或反射後會得到另一個解，如果將它們視為相同解，則只有12個解。(線上解題可以參考 這裡) 

解題說明 : 
要解決N-皇后問題 (在此N=8), 首先於棋盤中第一行的第一個位置入一個新皇后, 接下來在第二行依照第一列...到第N列順序置入新皇后, 如果置入的新皇后不會被之前放置的皇后吃掉, 則接著找下一行的皇后位置, 而找到皇后位置後就放入堆疊, 方對比對是否被之前放置的皇后吃掉使用. 一直到每一行的皇后都被找到就算是找到一組解, 而這種方式就是一種回溯演算法的應用概念. 也就是說 N-皇后問題的解答就是配合堆疊及回溯兩種資列結構的概念, 以逐行(或逐列)來找新皇后的位置 (如果找不到, 就回溯到前一行找尋前一個皇后另一個新的位置, 以此類推), 以下是8 皇后問題的一組解 : 
 

範例代碼 : 
* QueneChess.h 代碼 : 

view plaincopy to clipboardprint?

1. #ifndef _DS_QUENECHESS  
2. #define _DS_QUENECHESS  
3. #include   
4. using namespace std;  
5.   
6. #define EIGHT 8  
7. #define TRUE 1  
8. #define FALSE 0  
9.   
10. void print_table();  
11. void decide_position(int value);  
12.   
13. #endif  

* QueneChess.cpp 代碼 : 

view plaincopy to clipboardprint?

1. #include "QueneChess.h"  
2.   
3. int quene[EIGHT]; // 存放8 個皇后  
4. int number=0; // 計算組共幾組解  
5. int attack(int, int);  
6.   
7. void print_table(){  
8.     number+=1;  
9.     cout << endl;  
10.     cout << "八皇后問題的第" << number << "組解" << endl << "\t";  
11.     for(int x=0; x// 決定 row  
12.         for(int y=0; y// 決定 col  
13.             if(x == quene[y]) // 在 row:x 皇后出現在 col:y 或在 col:y 皇后出現在 row:x  
14.                 cout << "";  
15.             else  
16.                 cout << "<->";            
17.         }  
18.         cout << endl << "\t";  
19.     }  
20.     system("pause");  
21. }  
22.   
23. // 決定某個column 的皇后所在 row  
24. void decide_position(int col) {  
25.     int row=0;  
26.     while(row
27.         // 是否受到攻擊的判斷式  
28.         if(attack(row, col)!=1) { // 未受攻擊  
29.             cout << "Find Quene in col:" << col << ", row:" << row << endl;  
30.             quene[col] = row;  
31.             if(col==7) // 每列的解皆以找出  
32.                 print_table();  
33.             else {  
34.                 cout << "\t>>Decide col:" << col+1 << endl;  
35.                 decide_position(col+1); // 決定下一列解  
36.             }  
37.         }  
38.         row++;  
39.     }  
40.     cout << "\t>>Roll back to col:" << col-1 << endl;  
41. }  
42.   
43. // 若遭受攻擊則返回1, 否則返回0  
44. int attack(int row, int col) {  
45.     int i=0, atk=FALSE;  
46.     int offset_row=0, offset_col=0;  
47.     while((atk!=1) && i
48.         offset_col = abs(col-i);  
49.         offset_row = abs(quene[i] - row);  
50.         if((quene[i]==row) || (offset_row == offset_col)) // 如果與之前設定的皇后在同一 row, 或是在同一對角線上則 attack  
51.             atk = TRUE;   
52.         i++;  
53.     }  
54.     return atk;  
55. }  

* 呼叫演算法代碼 : 

view plaincopy to clipboardprint?

1. void ch04_08(bool b) {  
2.     if(b) {  
3.         decide_position(0);  
4.     }  
5. }  

執行結果 : 

...(以上省略)...
八皇后問題的第1組解
<-><-><-><-><-><-><->
<-><-><-><-><-><-><->
<-><-><-><-><-><-><->
<-><-><-><-><-><-><->
<-><-><-><-><-><-><->
<-><-><-><-><-><-><->
<-><-><-><-><-><-><->
<-><-><-><-><-><-><->

補充說明 : 
* 八皇后 Java 解 :