問題概述
八皇后問題是一個以西洋棋為背景的問題：如何能夠在 8×8 的西洋棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？為了達到此目的，任兩個皇后都不能處於同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的n皇后擺放問題：這時棋盤的大小變為n×n，而皇后個數也變成n。若且唯若 n = 1 或 n ≥ 4 時問題有解。
八皇后問題最早是由國際西洋棋棋手馬克斯·貝瑟爾於1848年提出。之後陸續有數學家對其進行研究，其中包括高斯和康托，並且將其推廣為更一般的n皇后擺放問題。八皇后問題的第一個解是在1850年由弗朗茲·諾克給出的。諾克也是首先將問題推廣到更一般的n皇后擺放問題的人之一。1874年，S.岡德爾提出了一個通過行列式來求解的方法，這個方法後來又被J.W.L.格萊舍加以改進。
艾茲格·迪傑斯特拉在1972年用這個問題為例來說明他所謂結構性編程的能力。
八皇后問題出現在1990年代初期的著名電子遊戲第七訪客中。
問題算法
C++
Pascal語言
Java算法
Erlang算法
圖形實現
簡述
對於八皇后問題的實現，如果結合動態的圖形演示，則可以使算法的描述更形象、更生動，使教學能產生良好的效果。下面是用Turbo C實現的八皇后問題的圖形程式，能夠演示全部的92組解。八皇后問題動態圖形的實現，主要應解決以下兩個問題。
C代碼頭檔案
主程式
介紹
八皇后問題，是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數學家高斯1850年提出：在8X8格的西洋棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處於同一行、同一列或同一斜線上，問有多少種擺法。 高斯認為有76種方案。1854年在柏林的象棋雜誌上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。計算機發明後，有多種方法可以解決此問題。
回溯算法
版本一
（a）為解決這個問題，我們把棋盤的橫坐標定為i，縱坐標定為j,i和j的取值範圍是從1到8。當某個皇后占了位置(i,j)時，在這個位置的垂直方向、水平方向和斜線方向都不能再放其它皇后了。
用語句實現，可定義如下三個整型數組：a,b,c。其中：
a[j-1]=1 第j列上無皇后
a[j-1]=0 第j列上有皇后
b[i+j-2]=1 (i,j)的對角線（右上至左下）無皇后
b[i+j-2]=0 (i,j)的對角線（右上至左下）有皇后
c[i-j+7]=1 (i,j)的對角線（左上至右下）無皇后
c[i-j+7]=0 (i,j)的對角線（左上至右下）有皇后
（b）為第i個皇后選擇位置的算法如下：
for(j=1;j<=8;j++) /*第j個皇后在第j行*/
if ((i,j)位置為空)） /*即相應的三個數組的對應元素值為1*/
{占用位置（i,j） /*置相應的三個數組對應的元素值為0*/
if i<8
為i+1個皇后選擇合適的位置；
else 輸出一個解
}
(2)圖形存取
在Turbo C語言中，圖形的存取可用如下標準函式實現：
size=imagesize(x1,y1,x2,y2) ;返回存儲區域所需位元組數。
arrow=malloc(size);建立指定大小的動態區域點陣圖，並設定一指針arrow。
getimage(x1,y1,x2,y2,arrow);將指定區域點陣圖存於一緩衝區。
putimage(x,y,arrow,copy)將點陣圖置於螢幕上以（x，y）左上角的區域。
(3)程式清單如下
#include#include#include#includechar n={'0','0'};/*用於記錄第幾組解*/int a,b,c,i;int h={127,177,227,277,327,377,427,477};/*每個皇后的行坐標*/int l={252,217,182,147,112,77,42,7}; /*每個皇后的列坐標*/void *arrow;void try(int i){int j;for (j=1;j<=8;j++)if (a[j-1]+b[i+j-2]+c[i-j+7]==3) /*如果第i列第j行為空*/{ a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;/*占用第i列第j行*/ putimage(h[i-1],l[j-1],arrow,COPY_PUT); /*顯示皇后圖形*/ delay(500);/*延時*/ if(i<8) try(i+1); else /*輸出一組解*/ { n++; if (n>'9') { n++;n="0"; } bar(260,300,390,340);/*顯示第n組解*/ outtextxy(275,300,n); delay(3000); }a[j-1]=1; b[i+j-2]=1; c[i-j+7]=1; putimage(h[i-1],l[j-1],arrow,XOR_PUT); /*消去皇后，繼續尋找下一組解*/ delay(500); }}int main(void){ int gdrive=DETECT,gmode,errorcode;unsigned int size; initgraph(&gdrive,&gmode,""); errorcode=graphresult(); if (errorcode!=grOk) { printf("Graphics error\n");exit(1); } rectangle(50,5,100,40); rectangle(60,25,90,33);/* 畫皇冠 */ line(60,28,90,28); line(60,25,55,15); line(55,15,68,25); line(68,25,68,10); line(68,10,75,25); line(75,25,82,10); line(82,10,82,25); line(82,25,95,15); line(95,15,90,25); size=imagesize(52,7,98,38); arrow=malloc(size); getimage(52,7,98,38,arrow); /* 把皇冠保存到緩衝區*/ clearviewport(); settextstyle(TRIPLEX_FONT, HORIZ_DIR, 4); setusercharsize(3, 1, 1, 1); setfillstyle(1,4); for (i=0;i<=7;i++) a=1; for (i=0;i<=14;i++) b=1; for (i=0;i<=23;i++) c=1; for (i=0;i<=8;i++) line(125,i*35+5,525,i*35+5); /* 畫棋盤 */ for (i=0;i<=8;i++) line(125+i*50,5,125+i*50,285); try(1); /* 調用遞歸函式 */ delay(3000); closegraph(); free(arrow);}#include#includestatic int a,i,j,sum=0,t=1,column_status,slash_status,back_slash_status;int main(){ void print_board(); void go_up(); memset(column_status,0,sizeof(column_status)); memset(slash_status,0,sizeof(slash_status)); memset(back_slash_status,0,sizeof(back_slash_status)); memset(a,0,sizeof(a)); for(i=1;i<=8;i++) for(j=t;j<=8;j++) if(column_status[j]==0 && slash_status[i-j+8]==0 && back_slash_status[i+j]==0) { a[i][j]=1; column_status[j]=1; slash_status[i-j+8]=1; back_slash_status[i+j]=1; if (i==8) { print_board(); if(t==8) { go_up(); i--; break; } elsej=t; } else { t=1;break; } } else if(j==8) { if (i==1)return 0; else { go_up(); i--; break; } } return 0;}void print_board(){ printf("第%d個方案為\n",++sum); for(i=1;i<=8;i++) { for(j=1;j<=8;j++) { if (a[i][j]==1) { printf("@ "); t=j; } else printf("* "); } printf("\n"); }}void go_up(){ i=i-1; for(j=1;j<=8;j++) { if(a[i][j]==1) { a[i][j]=0; column_status[j]=0; slash_status[i-j+8]=0; back_slash_status[i+j]=0; if (j==8) go_up(); else { t=j+1; break; } } }}易語言
版本二
.支持庫 iext3
.支持庫 iext
.程式集 啟動視窗程式集
.程式集變數皇后位置數組, 整數型, , "0", 如：皇后位置數組[j]=4，表示第j列，第皇后位置數組[j]行有皇后
.程式集變數 行數組, 整數型, , "0", 行數組[k]=1,表示第k行沒有皇后
.程式集變數 右高左低數組, 整數型, , "0", 右高左低數組[k]=1,表示第k條右高左低的斜線上沒有皇后
.程式集變數 左高右低數組, 整數型, , "0", 左高右低數組[k]=1,表示第k條左高右低的斜線上沒有皇后
.程式集變數 棋盤行列值, 整數型, , , 棋盤規模變數
.子程式 __啟動視窗_創建完畢
' 使用算法：遞歸法
' 問題：N後問題
' 問題描述：
'西洋棋中皇后可以攻擊所在行，列，斜線上的每一個位置，按照此規則要在一個n*n的棋盤上放n個皇后使每一個皇后都不互相攻擊
' 問題分析：
' （1） 引入1個數組模擬棋盤上皇后的位置
' 引入3個工作數組
' 行數組[k]=1,表示第k行沒有皇后
' 右高左低數組[k]=1,表示第k條右高左低的斜線上沒有皇后
' 左高右低數組[k]=1,表示第k條左高右低的斜線上沒有皇后
' 觀察棋盤找到規律
' 同一右高左低的斜線上的方格，它們的行號和列號之和相等；
' 同一左低右高的斜線上的方格，它們的行號和列號只差相等；
' 開始時，所有行和斜線上都沒有皇后，從第一列的第一行配置第一個皇后開始，在第m列的皇后位置數組[m]行放置了一個合理的皇后之後，準備考察第m+1列時，在數組行數組[]，右高左低數組[]，左高右低數組[]中為第m列，皇后位置數組[m]的位置設定有皇后標誌
' 如果按此放置位置得不到結果，則把當前列中的有皇后標記改為無皇后標記。
' 依次類推
' 當在棋盤最後一列上也找到合適的位置後得到結果。
' 通過上面規律可以推導出結果。
' 備註：
.子程式 __啟動視窗_尺寸被改變
問題編輯框.寬度 = 高級選擇夾1.寬度 － 16
問題編輯框.高度 = 高級選擇夾1.高度 － 43
分析編輯框.寬度 = 問題編輯框.寬度
分析編輯框.高度 = 問題編輯框.高度
分組框1.寬度 = 高級選擇夾1.寬度 － 18
分組框1.高度 = 高級選擇夾1.高度 － 36
超級列表框1.寬度 = 分組框1.寬度 － 184
超級列表框1.高度 = 分組框1.高度 － 33
.子程式_計算圖形按鈕_被單擊
.局部變數局部計次變數, 整數型, , , 在計次循環中記錄循環次數
.局部變數局部計次變數2, 整數型
.局部變數 返回值, 整數型, , , 返回是否放置所有皇后成功
' 清空列表框
.計次循環首 (超級列表框1.取列數 (), )
超級列表框1.刪除列 (0)
.計次循環尾 ()
.計次循環首 (超級列表框1.取表項數 (), )
超級列表框1.刪除表項 (0)
.計次循環尾 ()
' 獲得輸入棋盤規模數據
棋盤行列值 = 到數值 (輸入編輯框.內容)
.如果真 (棋盤行列值 < 1) ' 棋盤不能為0或負數
輸入編輯框.內容 = “4”
返回 ()
.如果真結束
' 如果輸入的棋盤規模過大提示是否等待
.如果真 (棋盤行列值 > 28)
.如果真 (信息框 (“您輸入的數值過大，處理數據時程式將會有一段時間無回響，是否繼續？”, #是否鈕 + #詢問圖示, “請問：”) ≠ #是鈕)
' 如果不想等待很長時間則返回
返回 ()
.如果真結束
.如果真結束
' 根據的到值定義棋盤行列，定義相關兩斜行的值
重定義數組(行數組, 假, 棋盤行列值)
重定義數組(右高左低數組, 假, 2 × 棋盤行列值)
重定義數組(左高右低數組, 假, 2 × 棋盤行列值)
重定義數組(皇后位置數組, 假, 棋盤行列值)
' 行數組 =1，表示第1行沒有皇后
.計次循環首 (棋盤行列值, 局部計次變數)
行數組 [局部計次變數] = 1
.計次循環尾 ()
' 右高左低數組=1，表示第1條右高左低的斜線上沒有皇后
' 左高右低數組=1，表示第1條左高右低的斜線上沒有皇后
.計次循環首 (2 × 棋盤行列值, 局部計次變數)
右高左低數組 [局部計次變數] = 1
左高右低數組 [局部計次變數] = 1
.計次循環尾 ()
' 從第一列開始找出合適的放置方法
返回值 = 皇后問題子程式(1)
.判斷開始 (返回值 = 1)
標籤2.標題 = “找到結果” ' 得到結果顯示在超級列表框中
超級列表框1.插入列 (, “0”, , , , )
超級列表框1.置列寬 (0, 30)
' 畫棋盤列
.計次循環首 (棋盤行列值, 局部計次變數)
超級列表框1.插入列 (, 到文本 (局部計次變數), , , , )
超級列表框1.置列寬 (局部計次變數, 30)
.計次循環尾 ()
' 畫棋盤行
.計次循環首 (棋盤行列值, 局部計次變數)
超級列表框1.插入表項 (, 到文本 (局部計次變數), , , , )
.計次循環尾 ()
' 顯示排列結果
.計次循環首 (棋盤行列值, 局部計次變數)
.計次循環首 (棋盤行列值, 局部計次變數2)
' 如果當前行列坐標上有皇后
.判斷開始 (皇后位置數組 [局部計次變數] = 局部計次變數2)
超級列表框1.置標題 (局部計次變數2 － 1, 局部計次變數, “皇”)
.默認
超級列表框1.置標題 (局部計次變數2 － 1, 局部計次變數, “*”)
.判斷結束
.計次循環尾 ()
.計次循環尾 ()
.默認
標籤2.標題 = “沒有合適結果”
.判斷結束
.子程式皇后問題子程式, 整數型, , 在n*n棋盤的第k列上找合理的皇后放置位置
.參數 當前判斷列, 整數型, , 當前在試探位置所在的列
.局部變數局部計次變數, 整數型, , , 試探合理位置時記錄當前的行
.局部變數結果控制變數, 整數型, , , 找到結果變數為1，沒有結果變數為0
局部計次變數= 1
結果控制變數 = 0
.判斷循環首 (結果控制變數 = 0 且 局部計次變數 ≤ 棋盤行列值) ' 沒有找到合理的解，並且還有沒試過的行，繼續循環
.如果真 (行數組 [局部計次變數] = 1 且 右高左低數組 [當前判斷列 + 局部計次變數] = 1 且 左高右低數組 [棋盤行列值 + 當前判斷列 － 局部計次變數] = 1) ' 是否在行，列，兩斜線上都沒有放置過皇后
皇后位置數組 [當前判斷列] = 局部計次變數
'數組值等於 0，表示已經有皇后
行數組 [局部計次變數] = 0
右高左低數組 [當前判斷列 + 局部計次變數] = 0
左高右低數組 [棋盤行列值 + 當前判斷列 － 局部計次變數] = 0
.判斷開始 (當前判斷列 = 棋盤行列值)
返回 (1) ' 如果已經是最後一列，找到解，返回 1
.默認
結果控制變數 =皇后問題子程式 (當前判斷列 + 1) ' 不是最後列，到下一列去放皇后，返回是否能放置皇后的信息
.判斷結束
行數組 [局部計次變數] = 1
右高左低數組 [當前判斷列 + 局部計次變數] = 1
左高右低數組 [棋盤行列值 + 當前判斷列 － 局部計次變數] = 1
.如果真結束
局部計次變數= 局部計次變數 + 1
.判斷循環尾 ()
返回 (結果控制變數) ' 返回最終是否有解的信息
循環實現* 數據表示
* 用一個 8 位的 8 進制數表示棋盤上皇后的位置：
* 比如：45615353 表示：
* 第0列皇后在第4個位置
* 第1列皇后在第5個位置
* 第2列皇后在第6個位置
* 。。。
* 第7列皇后在第3個位置
*
* 循環變數從 00000000 加到 77777777 （8進制數）的過程，就遍歷了皇后所有的情況
* 程式中用八進制數用一個一維數組data[] 表示
*
* 檢測衝突：
* 橫列衝突：data == data[j]
* 斜列衝突：(data+i) == (data[j]+j) 或者 (data-i) == (data[j]-j)
*
* 好處
* 採用循環，而不是遞規，系統資源占有少
* 可計算 n皇后問題
* 把問題線性化處理，可以把問題分塊，在分散式環境下用多台計算機一起算。
*
* ToDo
* 枚舉部分還可以進行最佳化，多加些判斷條件速度可以更快。
* 輸出部分可以修改成棋盤形式的輸出
*/public class Queen {int size;int resultCount;public void compute ( int size ) {this.size = size;resultCount = 0;int data[] = new int[size];int count; // 所有可能的情況個數int i,j;// 計算所有可能的情況的個數count = 1;for ( i=0 ; icount = count * size;}// 對每一個可能的情況for ( i=0 ; i// 計算這種情況下的棋盤上皇后的擺放位置，用 8 進制數表示// 此處可最佳化int temp = i;for ( j=0 ; jdata [j] = temp % size;temp = temp / size;}// 測試這種情況是否可行，如果可以，輸出if ( test(data) )output( data );}}/** 測試這種情況皇后的排列是否可行**/public boolean test( int[] data ) {int i,j;for ( i=0 ; ifor ( j=i+1 ; j// 測試是否在同一排if ( data == data[j] )return false;// 測試是否在一斜線if ( (data+i) == (data[j]+j) )return false;// 測試是否在一反斜線if ( (data-i) == (data[j]-j) )return false;}}return true;}/** 輸出某種情況下皇后的坐標**/public void output ( int[] data ) {int i;System.out.print ( ++resultCount + ": " );for ( i=0 ; iSystem.out.print ( "(" + i + "," + data + ") " );}System.out.println ();}public static void main(String args[]) {(new Queen()).compute( 8 );}}
Qbasic版
10 I = 1
20 A(I) = 1
30 G = 1
40 FOR K = I - 1 TO 1 STEP -1
50 IF A(I) = A(K) THEN 70
60 IF ABS(A(I) - A(K)) <> I - K THEN 90
70 G = 0
80 GOTO 100
90 NEXT K
100 IF I <> 8 THEN 180
110 IF G = 0 THEN 180
120 FOR L = 1 TO 8
130 PRINT USING “##”; A(L);
140 NEXT L
150 PRINT “*”;
160 M = M + 1
170 IF M MOD 3 = 0 THEN PRINT
180 IF G = 0 THEN 230
190 IF I = 8 THEN 230
200 I = I + 1
210 A(I) = 1
220 GOTO 30
230 IF A(I) < 8 THEN 270
240 I = I - 1
250 IF I = 0 THEN 290
260 GOTO 230
270 A(I) = A(I) + 1
280 GOTO 30
290 PRINT
300 PRINT “SUM=”; USING “##”; M;
310 PRINT
320 END
高效解法
//8 Queen遞歸算法
//如果有一個Q 為 chess=j;
//則不安全的地方是 k行 j位置,j+k-i位置,j-k+i位置
class Queen8{
static final int QueenMax = 8;
static int oktimes = 0;
static int chess[] = new int[QueenMax];//每一個Queen的放置位置
public static void main(String args[]){
for (int i=0;iplacequeen(0);
System.out.println("\n\n\n八皇后共有"+oktimes+"個解法 made by yifi 2003");
}
public static void placequeen(int num){ //num 為當前要放置的行數
int i=0;
boolean qsave[] = new boolean[QueenMax];
for(;i//下面先把安全位數組完成
i=0;//i 是要檢查的數組值
while (iqsave[chess]=false;
int k=num-i;
if ( (chess+k >= 0) && (chess+k < QueenMax) ) qsave[chess+k]=false;
if ( (chess-k >= 0) && (chess-k < QueenMax) ) qsave[chess-k]=false;
i++;
}
//下面歷遍安全位
for(i=0;iif (qsave==false)continue;
if (numchess[num]=i;
placequeen(num+1);
}
else{ //num is last one
chess[num]=i;
oktimes++;
System.out.println("這是第"+oktimes+"個解法 如下:");
System.out.println("第n行: 1 2 3 4 5 6 7 8");
for (i=0;iString row="第"+(i+1)+"行: ";
if (chess==0);
else
for(int j=0;jrow+="++";
int j = chess;
while(jSystem.out.println(row);
}
}
}
//歷遍完成就停止
}
}
c#非遞歸實現
思路
採用的思路大致是這樣：
將一個皇后向下移動一個位置；
如果沒有成功移動（超出邊界），失敗；
如果成功移動，則判斷當前位置是否可用？如果不可用，則重做 1；
繼續給下一個皇后安排位置。
結束條件
如果第一個皇后的所有位置都嘗試完畢仍然沒有可用的解決方案或者最後一個皇后已經安排完畢。
代碼
// AppEntry.csusing System;namespace Chenglin{ class AppEntry { static void Main(string[] args) { int queenNumber = 8; QueenRowCollection q = new QueenRowCollection(queenNumber); bool flag; DateTime timeStarted = DateTime.Now; flag = q.PositionQueens(); TimeSpan ts = DateTime.Now.Subtract( timeStarted ); if( flag ) { Console.WriteLine( q.ToString() ); } else { Console.WriteLine( "Failed" ); } Console.WriteLine( " seconds has been elapsed.", ts.TotalSeconds ); } }}// QueenRowCollection.csusing System;using System.Text;namespace Chenglin{ public class QueenRowCollection { public QueenRowCollection( int numberOfQueens ) { this.numberOfQueens = numberOfQueens; this.rows = new QueenRow[ numberOfQueens ]; } } public bool PositionQueens() { return PositionQueen( 0 ); } private bool PositionQueen( int row ) { if( row>=this.numberOfQueens ) { return true; } QueenRow q = rows[row]; while(q.MoveNext()) { if( PositionAvailable( row, q.CurrentPosition ) ) { // An available position has been found for the current queen, // and try to find a proper position for the next queen. // // If no available position can be found for the next queen, // the current queen should move to the next position and try again. // if( PositionQueen( row+1 ) ) { // Both the current queen and the next queen // have found available positions. // return true; } } } // No position is available for the current queen, // return false; } private bool PositionAvailable( int row, int column ) { for( int i=row-1; i>=0; i-- ) { if( rows.PositionOccupied( column ) ) return false; if( rows.PositionOccupied( column-(i-row) ) ) return false; if( rows.PositionOccupied( column+(i-row) ) ) return false; } return true; } public override string ToString() { StringBuilder s = new StringBuilder(); foreach( QueenRow q in rows ) { s.AppendFormat( "", q, Environment.NewLine ); } return s.ToString(); } private int numberOfQueens; private QueenRow [] rows; }}
1// QueenRow.cs
2using System;
3using System.Text;
4
5namespace Chenglin
6{
7 public class QueenRow
8 {
9 public QueenRow( int numberOfPositions )
10 {
11 this.numberOfPositions = numberOfPositions;
12 this.currentPosition = -1;
13 this.columns = new bool[ numberOfPositions ];
14 }
15
16 public bool MoveNext(){
17 if( currentPosition>=0 && currentPosition18 columns[currentPosition] = false;
19 }
20
21 if( currentPosition22 currentPosition ++;
23 columns[currentPosition] = true;
24 return true;
25 }
26 else {
27 currentPosition = -1;
28 return false;
29 }
30 }
31
32 public bool PositionOccupied( int column ){
33 if( column<0 || column>=numberOfPositions ){
34 return false;
35 }
36
37 return columns[column];
38 }
39
40 public override string ToString()
41 {
42 StringBuilder s = new StringBuilder();
43
44 foreach( bool b in columns ){
45 s.AppendFormat( " ", (b ? "*" : "-") );
46 }
47
48 return s.ToString();
49 }
50
51 public int CurrentPosition
52 {
53 get { return currentPosition; }
54 }
55
56 private int currentPosition;
57 private int numberOfPositions;
58 private bool [] columns;
59 }
60}
遞歸實現思路：
按列分別安排皇后(Q)，Q數目可隨意指定（由於StackOverFlowException，只能到8）。
Q1可以放在任何位置；
然後嘗試Q2，因為Q1的限制，Q2必須排除第二列與Q1行數插值大於2的位置；
依次嘗試Qm... 如果Qm上沒有剩餘可用位置，則返回Qm-1，同時使Qm-1 放棄剛才使用位置；
當到達結尾Qn時，成功放置，則存儲所有位置，作為一種解法；
當Q1嘗試過首列所有位置後，算法結束。
結果統計並羅列所有解法。
堆疊修改：
“editbin /stack:4048000 D:\aa\ConsoleApplication2.exe”
代碼：
using System;
using System.Collections.Generic;
classMainClass
{
staticvoid Main()
{
int queens = int.Parse(Console.ReadLine());
List allPositions = GetAllPositions(queens);
int column = 0;
List> solutions = newList>();
EightQueens(queens, allPositions, column, newStack(), solutions);
for (int i = 0; i < solutions.Count; i++)
{
DisplayPositions(solutions[i]);
}
Console.WriteLine(solutions.Count);
Console.Read();
}
#region EightQueens
classStack
{
publicList CurrentPositions = newList();
List>> stack = newList>>();
publicvoid push(int i, List p )
{
stack.Add(newKeyValuePair>(i, p));
}
publicKeyValuePair> pop()
{
KeyValuePair> p = stack[stack.Count - 1];
stack.RemoveAt(stack.Count - 1);
return p;
}
publicvoid ClearFromKey(int key)
{
int idx = stack.FindIndex(a=>a.Key == key);
if (idx > -1)
{
stack.RemoveRange(idx, stack.Count - idx);
}
}
publicList>> StackList
{
get
{
returnthis.stack;
}
}
}
classPosition
{
publicint left;
publicint right;
public Position(int left, int right)
{
this.left = left;
this.right = right;
}
publicint LeftDistence(Position p)
{
returnMath.Abs(this.left - p.left);
}
publicint RightDistence(Position p)
{
returnMath.Abs(this.right - p.right);
}
publicint QueenNumber = -1;
publicbool HasQueen
{
get
{
return QueenNumber != -1;
}
}
}
staticKeyValuePair EightQueens(int queens, List allPositions, int column, Stack stack, List> solutions)
{
if (column == queens)
{
List newLst = newList();
if(solutions.Count > 0)
{
for(int i = 0 ; i < solutions[solutions.Count - 1].Count -1 ; i++)
{
newLst.Add(solutions[solutions.Count - 1][i]);
}
}
solutions.Add(newLst);
return EightQueens(queens, allPositions, column -1, stack, solutions);
}
if (column == 0)
{
stack.ClearFromKey(1);
if (solutions.Count > 0 && solutions[solutions.Count - 1].Count != queens)
{
solutions.RemoveAt(solutions.Count - 1);
}
solutions.Add(newList());
}
List results;
if (solutions.Count > 0)
{
results = solutions[solutions.Count - 1];
}
else
{
results = newList();
}
List newPositions = newList();
if (stack.StackList.Exists(a => a.Key == column))
{
newPositions = stack.StackList.Find(a => a.Key == column).Value;
if (newPositions.Count > 0)
{
newPositions.RemoveAt(0);
}
}
else
{
newPositions = allPositions.FindAll(a => a.left == column);
newPositions = FilterPositions(newPositions, results);
stack.push(column, newPositions);
}
if (newPositions.Count > 0)
{
newPositions.QueenNumber = column;
results.Add(newPositions);
column = column + 1;
return EightQueens(queens, allPositions, column, stack, solutions);
}
else
{
stack.ClearFromKey(column);
if (stack.StackList.Count > 0 && stack.StackList.Find(a => a.Key == 0).Value.Count > 0)
{
if (results.Count > 0)
{
results.RemoveAt(results.Count - 1);
}
return EightQueens(queens, allPositions, column - 1, stack, solutions);
}
else
{
if (solutions.Count > 0)
{
solutions.RemoveAt(solutions.Count - 1);
}
returnnewKeyValuePair(true, 0);
}
}
}
staticList GetAllPositions(int queens)
{
List positions = newList();
for (int i = 0; i < queens; i++)
{
for (int j = 0; j < queens; j++)
{
positions.Add(newPosition(i, j));
}
}
return positions;
}
staticListFilterPositions(Listoriginal, Position newPosition)
{
return original.FindAll(a => CheckPosition(a, newPosition));
}
staticList original, List newPositions)
{
if (newPositions == null || newPositions.Count == 0)
{
return original;
}
List ps = newList();
foreach(Position p in newPositions)
{
original.RemoveAll(a => ! CheckPosition(a, p));
}
foreach (Position p in original)
{
ps.Add(p);
}
return ps;
}
staticBoolean CheckPosition(Position newPosition, Position targetPosition)
{
int left = newPosition.LeftDistence(targetPosition);
int right = newPosition.RightDistence(targetPosition);
if (left < 1 || right < 1 || left == right)
{
returnfalse;
}
returntrue;
}
staticvoid DisplayPositions(List positions)
{
for (int i = 0; i < positions.Count; i++)
{
Console.Write(positions[i].left);
Console.Write(positions[i].right + ",");
}
Console.WriteLine();
}
#endregion
}
C++代碼#includeusing namespace std;int width=8,lim=(1<<1,(rd|t)>>1); //往棋盤的下一行遞歸,左斜線的限制往左，右斜線往右，可以畫圖看看 }}int main(){ queen(0,0,0); // cout< return 0;}C++另外一種方法
#include using namespace std;int a; int b; int c=0;bool flag(int pos){ int i; for(i=0;i<<<"種方法"; system("pause"); return 0;}Python
#!/usr/bin/env python# 用一位數組模擬，數組中的值代表皇后所在的列，則皇后所有的位置# 的解空間是[0,1,2,3,4,5,6,7]的所有排列。對某一排列肯定滿足不在# 同行同列的要求，只需要判斷對任意兩皇后不在斜對角線上就行# 即： |i - j| != |array[i] - array[j]|def check_diagonal(array): for i in range(len(array)): for j in range(i+1, len(array)): if j-i == abs(array[i] - array[j]): return False return Truedef permutation(array, begin_index): result = 0 if begin_index >= len(array)-1: if check_diagonal(array): #print array result += 1 else: for i in range(begin_index, len(array)): array[begin_index], array[i] = array[i], array[begin_index] result += permutation(array, begin_index+1) array[begin_index], array[i] = array[i], array[begin_index] return resultdef queen(num): array = range(num) return permutation(array, 0)if __name__ == '__main__': print queen(8)
PHP實現
思路：將皇后的位置用一個一維數組保存起來，類似棧，棧底從0開始
/**
* @param $j 下一個皇后可能所在的位置
* @param $queen 存放之前符合所有條件的皇后的位置
* @return boolean 衝突時返回true
*/
function isConflict($j,$queen)
{
for($i = 0,$len = count($queen); $i<$len; $i++)
{
//與$queen中任意皇后在同一列或對角線上
if(in_array(abs($j-$queen[$i]),array(0,($len-$i))))
return true;
}
return false;
}
/**
* 回溯
*/
function backTracking(&$queen,&$j,$num)
{
$j = array_pop($queen);//將棧頂退出，下次循環就$j=$j+1,也就是從下個位置開始
if($j == $num-1)//若退出的是上一行的最後一列
{
if ($queen)//當棧不為空時,繼續回退
{
$j = array_pop($queen);
}
else//棧已空,遍歷結束
{
$j = $num -1;
}
}
}
/**
* @param $num 皇后個數
*
*/
function queens($num)
{
$queen = array();//存放一種結果
$queens = array();//存放所有結果
for($j=0;$j<$num;$j++)
{
if (isConflict($j,$queen))
{
if($j == $num-1)
{
backTracking($queen,$j,$num);
}
}
else
{
array_push($queen,$j);//沒有任何衝突，入棧
$j = -1;//下次循環時, $j = 0
if(count($queen) == $num)//棧滿了，已找到了符合所有條件的所有皇后，保存起來。
{
$queens[] = $queen;
backTracking($queen,$j,$num);
}
}
}
return $queens;
}
PASCAL
program bahuanghou;
var ans:array[1..8] of integer; //記錄答案的數組，記錄在第1到第8行皇后所在的列；
lie:array[1..8] of boolean; //記錄1到8中某列是否已經被另一個皇后占用；
zx:array[2..16] of boolean; //正斜線（左下向右上）數組，該斜線特點為：斜線上每一格的行加列的和一定，和為從2到16.。故可用2到16來表示這15條正斜線，於是該數組記錄了2到16中某條正斜線是否已經被另一個皇后占用；
fx:array[-7..7] of boolean; //反斜線（左上向右下）數組，該斜線特點為：斜線上每一格的行減列的差一定，差為從-7到7。故可用-7到7來表示這15條反斜線，於是該數組記錄了2到16中某條正斜線是否已經被另一個皇后占反；
temp:integer; //記錄總方案數；
procedure print; //該子程式負責輸出方案；
var i:integer;
begin
write('zuobiao');
for i:=1 to 8 do write(' (',i,',',ans[i],')'); //i代表行，ans[i]代表列；
writeln;
end;
procedure search(i:integer); //i為行，即表示放到了第幾個皇后（因為一行有且只有1個皇后);
var j:integer；
begin
if i=9 then //遞歸出口，當搜尋到第九行時，便得到一種方案；
begin
print; //輸出該方案；
inc(temp); //每輸出（得到）一種方案，總方案數變加1；
exit; //退出；
end;
for j:=1 to 8 do if not lie[j] and not zx[i+j] and not fx[i-j] then //當前位置，該列，正斜線，反斜線上均未被另一個皇后占用，即可以擺放一個皇后；
begin
lie[j]:=true; //設定標誌，該行
zx[i+j]:=true; // 該正斜線
fx[i-j]:=true; // 該反斜線上已被皇后占用，不可再放皇后；
ans[i]:=j; //記錄答案（第i行皇后所在列j）；
search(i+1); //實行下一層遞歸；
lie[j]:=false; //恢復標誌（回溯）；
zx[i+j]:=false;
fx[i-j]:=false;
end;
end;
begin //主程式；
temp:=0; //給總方案數設初值為“0”；
fillchar(lie,sizeof(lie),0); //分別給列
fillchar(zx,sizeof(zx),0); // 正斜線
fillchar(fx,sizeof(fx),0); // 反斜線數組設初值為“假”
search(1); //從第一行開始進行搜尋；
writeln(temp); //再輸出總方案數；
end.
SHELL
#/bin/bash
canSet() { # 檢查是否可放下皇后的子程式.
for ((n=0;n
((P[$n] == x)) && return 1 # 檢查是否同一行, 如果是返回1 false
((P[$n] == x - n + y )) && return 1 #檢查斜行.
((P[$n] == x + n - y )) && return 1 #檢查另一方向斜行.
done
return 0 # 返回成功.
}
# init
y=0 # y 是行,
for((i=0;i<8;i++)) ;do
P[$i]=-1 # p 是座位array , -1是不在棋盤上.
done
while (((y<8)&&(y>=0)));do #如果y>=8, 即找到結果, 如果y<0, 即找不到結果, 退出回卷
# echo ${P[*]}; # 打開這一註解,可看script 運行過程
f=0 # 設flag = 0, 用它檢查否一整能不能放下皇后
s=${P[$y]}+1 # 每一行皇后放下的列位罝+1
for ((x=s;x<8;x++)); do #其他shell 用 for x in seq $s 7
if canSet ;then #如果可放下, 則
P[$y]=$x #記下皇后位罝
((y++)) # 行位罝加1, 如用其他shell, 用 y=`expr $y + 1`代替
f=1 #設flag=1,即可效皇后.
break #處理下一個皇后
fi
done
if [ $f -eq 0 ];then # 如果整行都不能放下皇后.則
P[$y]=-1 #將皇后由棋盤上拿下.
((y--)) #行位罝-1.
fi
done
echo ${P[*]}; 列印數據
獨立解
八皇后問題在92個解中，很多解在棋盤上有對稱關係，每一個棋子都有8個對稱位置，如果一個解和另外一個解所有的棋子都呈同一種對稱，那么這兩個解之間就是對稱關係。例如右邊兩個解實際上沿著垂直軸翻轉，就是一個，因此不是獨立的。相互間沒有對稱關係的解是獨立解。雖然一個解可以有8個對稱位置，但是有些解經過對稱操作後和沒有操作前是一樣的。
八皇后問題在一個標準的8×8的棋盤中，92個解當中有12個解是獨立的。8×8棋盤的獨立解如圖所示。
如果把棋盤從8×8變成N×N, 八皇后問題就變成了N皇后問題。N從4以上都有解，並分別有相應的獨立解。
下面是皇后的數目於解數目的關係
皇后數獨立解全部解111
4
12521061476408129294635210927241134126801217871420013923373712144575236559
比較特殊的是，皇后6x6棋盤的解比5x5少，其餘解的數目隨著皇后數目增加。但似乎無數學表達式可以描述。
pascal的解法是
var
i,k,n,h:longint;
x:array[1..1000] of longint;
function p1(k:longint):boolean;
begin
p1:=true;
for i:=1 to (k-1) do
if (x[i]=x[k]) or ((abs(x[i]-x[k]))=(abs(i-k))) then p1:=false;
end;
procedure p2;
begin
h:=h+1;
end;
procedure p3(k:longint);
var i:integer;
begin
if (k=n+1) then
begin
p2;
exit;
end;
for i:=1 to n do
begin
x[k]:=i;
if p1(k) then p3(k+1);
end;
end;
begin
readln(n);
p3(1);
write(h);
end.
VB實現
主要利用遞推思想 挨個判斷是否可放置皇后若是 繼續放置下一個 否則尋找其餘位置
支持庫 iext3
.支持庫 iext
.程式集啟動視窗程式集
.程式集變數皇后位置數組, 整數型, , "0", 如：皇后位置數組[j]=4，表示第j列，第皇后位置數組[j]行有皇后
.程式集變數 行數組, 整數型, , "0", 行數組[k]=1,表示第k行沒有皇后
.程式集變數 右高左低數組, 整數型, , "0", 右高左低數組[k]=1,表示第k條右高左低的斜線上沒有皇后
.程式集變數 左高右低數組, 整數型, , "0", 左高右低數組[k]=1,表示第k條左高右低的斜線上沒有皇后
.程式集變數 棋盤行列值, 整數型, , , 棋盤規模變數
.子程式__啟動視窗_創建完畢
' 使用算法：遞歸法
' 問題：N後問題
' 問題描述：
'西洋棋中皇后可以攻擊所在行，列，斜線上的每一個位置，按照此規則要在一個n*n的棋盤上放n個皇后使每一個皇后都不互相攻擊
' 問題分析：
' （1） 引入1個數組模擬棋盤上皇后的位置
' 引入3個工作數組
' 行數組[k]=1,表示第k行沒有皇后
' 右高左低數組[k]=1,表示第k條右高左低的斜線上沒有皇后
' 左高右低數組[k]=1,表示第k條左高右低的斜線上沒有皇后
' 觀察棋盤找到規律
' 同一右高左低的斜線上的方格，它們的行號和列號之和相等；
' 同一左高右低的斜線上的方格，它們的行號和列號只差相等；
' 開始時，所有行和斜線上都沒有皇后，從第一列的第一行配置第一個皇后開始，在第m列的皇后位置數組[m]行放置了一個合理的皇后之後，準備考察第m+1列時，在數組行數組[]，右高左低數組[]，左高右低數組[]中為第m列，皇后位置數組[m]的位置設定有皇后標誌
' 如果按此放置位置得不到結果，則把當前列中的有皇后標記改為無皇后標記。
' 依次類推
' 當在棋盤最後一列上也找到合適的位置後得到結果。
' 通過上面規律可以推導出結果。
' 備註：
.子程式 __啟動視窗_尺寸被改變
問題編輯框.寬度 = 高級選擇夾1.寬度 － 16
問題編輯框.高度 = 高級選擇夾1.高度 － 43
分析編輯框.寬度 = 問題編輯框.寬度
分析編輯框.高度 = 問題編輯框.高度
分組框1.寬度 = 高級選擇夾1.寬度 － 18
分組框1.高度 = 高級選擇夾1.高度 － 36
超級列表框1.寬度 = 分組框1.寬度 － 184
超級列表框1.高度 = 分組框1.高度 － 33
.子程式_計算圖形按鈕_被單擊
.局部變數局部計次變數, 整數型, , , 在計次循環中記錄循環次數
.局部變數局部計次變數2, 整數型
.局部變數返回值, 整數型, , , 返回是否放置所有皇后成功
' 清空列表框
.計次循環首 (超級列表框1.取列數 (), )
超級列表框1.刪除列 (0)
.計次循環尾 ()
.計次循環首 (超級列表框1.取表項數 (), )
超級列表框1.刪除表項 (0)
.計次循環尾 ()
' 獲得輸入棋盤規模數據
棋盤行列值 = 到數值 (輸入編輯框.內容)
.如果真 (棋盤行列值 < 1) ' 棋盤不能為0或負數
輸入編輯框.內容 = “4”
返回 ()
.如果真結束
' 如果輸入的棋盤規模過大提示是否等待
.如果真 (棋盤行列值 > 28)
.如果真 (信息框 (“您輸入的數值過大，處理數據時程式將會有一段時間無回響，是否繼續？”, #是否鈕 + #詢問圖示, “請問：”) ≠ #是鈕)
' 如果不想等待很長時間則返回
返回 ()
.如果真結束
.如果真結束
' 根據的到值定義棋盤行列，定義相關兩斜行的值
重定義數組(行數組, 假, 棋盤行列值)
重定義數組(右高左低數組, 假, 2 × 棋盤行列值)
重定義數組(左高右低數組, 假, 2 × 棋盤行列值)
重定義數組(皇后位置數組, 假, 棋盤行列值)
' 行數組 =1，表示第1行沒有皇后
.計次循環首 (棋盤行列值, 局部計次變數)
行數組 [局部計次變數] = 1
.計次循環尾 ()
' 右高左低數組=1，表示第1條右高左低的斜線上沒有皇后
' 左高右低數組=1，表示第1條左高右低的斜線上沒有皇后
.計次循環首 (2 × 棋盤行列值, 局部計次變數)
右高左低數組 [局部計次變數] = 1
左高右低數組 [局部計次變數] = 1
.計次循環尾 ()
' 從第一列開始找出合適的放置方法
返回值 = 皇后問題子程式(1)
.判斷開始 (返回值 = 1)
標籤2.標題 = “找到結果” ' 得到結果顯示在超級列表框中
超級列表框1.插入列 (, “0”, , , , )
超級列表框1.置列寬 (0, 30)
' 畫棋盤列
.計次循環首 (棋盤行列值, 局部計次變數)
超級列表框1.插入列 (, 到文本 (局部計次變數), , , , )
超級列表框1.置列寬 (局部計次變數, 30)
.計次循環尾 ()
' 畫棋盤行
.計次循環首 (棋盤行列值, 局部計次變數)
超級列表框1.插入表項 (, 到文本 (局部計次變數), , , , )
.計次循環尾 ()
' 顯示排列結果
.計次循環首 (棋盤行列值, 局部計次變數)
.計次循環首 (棋盤行列值, 局部計次變數2)
' 如果當前行列坐標上有皇后
.判斷開始 (皇后位置數組 [局部計次變數] = 局部計次變數2)
超級列表框1.置標題 (局部計次變數2 － 1, 局部計次變數, “皇”)
.默認
超級列表框1.置標題 (局部計次變數2 － 1, 局部計次變數, “*”)
.判斷結束
.計次循環尾 ()
.計次循環尾 ()
.默認
標籤2.標題 = “沒有合適結果”
.判斷結束
.子程式皇后問題子程式, 整數型, , 在n*n棋盤的第k列上找合理的皇后放置位置
.參數 當前判斷列, 整數型, , 當前在試探位置所在的列
.局部變數局部計次變數, 整數型, , , 試探合理位置時記錄當前的行
.局部變數結果控制變數, 整數型, , , 找到結果變數為1，沒有結果變數為0
局部計次變數= 1
結果控制變數 = 0
.判斷循環首 (結果控制變數 = 0 且 局部計次變數 ≤ 棋盤行列值) ' 沒有找到合理的解，並且還有沒試過的行，繼續循環
.如果真 (行數組 [局部計次變數] = 1 且 右高左低數組 [當前判斷列 + 局部計次變數] = 1 且 左高右低數組 [棋盤行列值 + 當前判斷列 － 局部計次變數] = 1) ' 是否在行，列，兩斜線上都沒有放置過皇后
皇后位置數組 [當前判斷列] = 局部計次變數
'數組值等於 0，表示已經有皇后
行數組 [局部計次變數] = 0
右高左低數組 [當前判斷列 + 局部計次變數] = 0
左高右低數組 [棋盤行列值 + 當前判斷列 － 局部計次變數] = 0
.判斷開始 (當前判斷列 = 棋盤行列值)
返回 (1) ' 如果已經是最後一列，找到解，返回 1
.默認
結果控制變數 =皇后問題子程式 (當前判斷列 + 1) ' 不是最後列，到下一列去放皇后，返回是否能放置皇后的信息
.判斷結束
行數組 [局部計次變數] = 1
右高左低數組 [當前判斷列 + 局部計次變數] = 1
左高右低數組 [棋盤行列值 + 當前判斷列 － 局部計次變數] = 1
.如果真結束
局部計次變數= 局部計次變數 + 1
.判斷循環尾 ()
返回 (結果控制變數) ' 返回最終是否有解的信息
循環實現*數據表示
* 用一個 8 位的 8 進制數表示棋盤上皇后的位置：
* 比如：45615353 表示：
* 第0列皇后在第4個位置
* 第1列皇后在第5個位置
* 第2列皇后在第6個位置
* 。。。
* 第7列皇后在第3個位置
*
* 循環變數從 00000000 加到 77777777 （8進制數）的過程，就遍歷了皇后所有的情況
* 程式中用八進制數用一個一維數組data[] 表示
*
* 檢測衝突：
* 橫列衝突：data == data[j]
* 斜列衝突：(data+i) == (data[j]+j) 或者 (data-i) == (data[j]-j)
*
* 好處
* 採用循環，而不是遞規，系統資源占有少
* 可計算 n皇后問題
* 把問題線性化處理，可以把問題分塊，在分散式環境下用多台計算機一起算。
*
* ToDo
* 枚舉部分還可以進行最佳化，多加些判斷條件速度可以更快。
* 輸出部分可以修改成棋盤形式的輸出
*/public class Queen {int size;int resultCount;public void compute ( int size ) {this.size = size;resultCount = 0;int data[] = new int[size];intcount; // 所有可能的情況個數int i,j;// 計算所有可能的情況的個數count = 1;for ( i=0 ; icount = count * size;}// 對每一個可能的情況for ( i=0 ; i// 計算這種情況下的棋盤上皇后的擺放位置，用 8 進制數表示// 此處可最佳化inttemp= i;for ( j=0 ; jdata [j] = temp % size;temp = temp / size;}// 測試這種情況是否可行，如果可以，輸出if (test(data) )output( data );}}/** 測試這種情況皇后的排列是否可行**/public boolean test( int[] data ) {int i,j;for ( i=0 ; ifor ( j=i+1 ; j// 測試是否在同一排if ( data == data[j] )returnfalse;// 測試是否在一斜線if ( (data+i) == (data[j]+j) )return false;// 測試是否在一反斜線if ( (data-i) == (data[j]-j) )return false;}}returntrue;}/** 輸出某種情況下皇后的坐標**/public void output ( int[] data ) {int i;System.out.print ( ++resultCount + ": " );for ( i=0 ; iSystem.out.print ( "(" + i + "," + data + ") " );}System.out.println ();}public static void main(String args[]) {(new Queen()).compute( 8 );}}
八皇后圖趣味數學
| 趣味數學以帶有強烈的遊戲色彩知名於世。歐拉就是通過對bridge-crossing之謎的分析打下了拓撲學的基礎。萊布尼茨也寫到過他在獨自玩插棍遊戲時分析問題的樂趣。希爾伯特證明了切割幾何圖形中的許多重要定理。馮·紐曼奠基了博弈論。最受大眾歡迎的計算機遊戲—生命是英國著名數學家康威發明的。愛因斯坦也收藏了整整一書架關於數學遊戲和數學謎的書。 |
