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

標籤

2010年10月2日 星期六

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

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

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

範例代碼 : 
* QueneChess.h 代碼 : 
  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 代碼 : 
  1. #include "QueneChess.h"  
  2.   
  3. int quene[EIGHT]; // 存放8 個皇后  
  4. int number=0// 計算組共幾組解  
  5. int attack(intint);  
  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. }  
* 呼叫演算法代碼 : 
  1. void ch04_08(bool b) {  
  2.     if(b) {  
  3.         decide_position(0);  
  4.     }  
  5. }  


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


補充說明 : 
八皇后 Java 解 :

沒有留言:

張貼留言

網誌存檔