八皇后VC圖形演示

    這幾天學VC界面編程，在VC在線上狂看教程，覺得有所長進，于是把以前的Java代碼用VC改寫了一下。問題還是那個老掉牙的問題，八皇后問題，老歸老，但我很喜歡，并試圖用各種方法來實現求解，出乎意料的是，同樣的算法，非遞歸實現的速度竟然比遞歸實現慢！下面是當時關于算法一些說明，是用Java實現的，不過用C還是J在思想上都是一樣的，如果需要J版的source可已發mail給我。

    

算法思想：回溯法，先在第1行放上一個皇后，然后在第2行合適的位置放上一個皇后，依次類推，如果8行都放滿了，說明找到了一個解，如果第好第i行的皇后后，第i+1行找不到合適的位置，這時就回到第i行，把第i行的皇后放到下一個位置，繼續嘗試下一行。如此反復，知道找到所有的解。注意，這種算法找的解可能有等價的，某些解可由別的解經過旋轉棋盤得到。

 

實現1：EightQueen.java

這是對上面的思想的一種經典實現方式，它使用了問題一個這樣的特性：假設棋盤上一條從左上到右下的斜線上的位置的坐標用（i，j）表示，那么這個i，j滿足下面方程：

(i-i0)/(j-j0) =1，即，i-j = i0-j0

其中i0，j0是這條線上任意一個位置。也就是說i-j的值只和斜線的起始位置有關，因此可以用一個數組來表示2n-1條左上到右下的斜線上是否有皇后。同樣可以確定一個表示從右上到左下的斜線的數組和豎線的數組：

  int[] queen;   /大小為n，queen[i] 表示第i行皇后的列的位置。

  boolean[] rk;  //大小2n-1，表示從右上到左下的斜線上有沒有皇后。

  boolean[] lk;  //大小2n-1，表示從左上到右下的斜線上有沒有皇后。

  boolean[] mk;  //大小n，mk[i]表示第第i列沒有皇后。

有了這3個數組，每放一個皇后就把相應位置的值設為真，當放下一個皇后時就可以參考這個數組來判斷某個位置能否放皇后。

 

實現2：QuickEightQueen.java

上面的算法可以做個小小的改進，每當我們在第i的某列放上一個皇后后，第i+1行改列就不可能再放了，因此每增加一行，要考慮的列就減少了一列，當回溯時再增加這列。為了高效實現增加和刪除，這里使用了整數鏈表來實現。

 

試驗結果：這是各個實現在14*14的棋盤上的運行結果（P4 2.4G/win2000/JDK1.5）：

文件名                       (ms)
 
EightQueen.java              4860
 
QuickEightQueen.java         2547
 
NREightQueen.java            4703
 
NRQuickEightQueen.java       2969
 
EQueen.java                  17234
 


 

其中以NR開頭的是非遞歸算法。EQueen.java是網上拷貝的一個非遞歸算法，沒有使用的EightQueen.java的思想。

 

此外，GraphEightQueen.java實現了一個圖形演示EightQueen.java工具。