標籤:演算法經典問題

八皇后問題,是一個古老而著名的問題,是回溯演算法的典型例題。該問題是十九世紀著名的數學家高斯1850年提出:在8X8格的國際象棋上擺放八個皇后,使其不能互相攻擊,即任意兩個皇后都不能處於同一行、同一列或同一斜線上,問有多少種擺法。 高斯認為有76種方案。1854年在柏林的象棋雜誌上不同的作者發表了40種不同的解,後來有人用圖論的方法解出92種結果。計算機發明后,有多種方法可以解決此問題。

1簡介

八皇后問題最早是由國際西洋棋棋手馬克斯·貝瑟爾於1848年提出。之後陸續有數學家對其進行研究,其中包括高斯和康托,並且將其推廣為更一般的n皇后擺放問題。八皇后問題的第一個解是在1850年由弗朗茲·諾克給出的。諾克也是首先將問題推廣到更一般的n皇后擺放問題的人之一。1874年,S.岡德爾提出了一個通過行列式來求解的方法,這個方法後來又被J.W.L.格萊舍加以改進。
艾茲格·迪傑斯特拉在1972年用這個問題為例來說明他所謂結構性編程的能力。
八皇后問題在1990年代初期的著名電子遊戲第七訪客和NDS平台的著名電子遊戲雷頓教授與不可思議的小鎮中都有出現。

2名詞解釋

八皇后問題是一個以國際象棋為背景的問題:如何能夠在 8×8 的國際象棋棋盤上放置八個皇后,使得任何一個皇后都無法直接吃掉其他的皇后?為了達到此目的,任兩個皇后都不能處於同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的n皇后擺放問題:這時棋盤的大小變為n×n,而皇后個數也變成n。當且僅當 n = 1 或 n ≥ 4 時問題有解。
Erlang
-module(queen).-export([printf/0, attack_range/2]).-define(MaxQueen, 4).%尋找字元串所有可能的排列%perms([]) ->% [[]];%perms(L) ->% [[H | T] || H <- L, T <- perms(L -- [H])].perms([]) ->[[]];perms(L) ->[[H | T] || H <- L, T <- perms(L -- [H]), attack_range(H,T) == []].printf() ->L = lists:seq(1, ?MaxQueen),io:format("~p~n", [?MaxQueen]),perms(L).%檢測出第一行的數字攻擊到之後各行哪些數字%left向下行的左側檢測%right向下行的右側檢測attack_range(Queen, List) ->attack_range(Queen, left, List) ++ attack_range(Queen, right, List).attack_range(_, _, []) ->[];attack_range(Queen, left, [H | _]) when Queen - 1 =:= H ->[H];attack_range(Queen, right, [H | _]) when Queen + 1 =:= H ->[H];attack_range(Queen, left, [_ | T]) ->attack_range(Queen - 1, left, T);attack_range(Queen, right, [_ | T]) ->attack_range(Queen + 1, right, T).C代碼頭文件
eigqueprob.h#include#define N 8 ""typedef struct{int line; "int row; "}ANSWER_TYPE;"typedef enum{notoccued = 0, "occued = 1 "}IFOCCUED;"IFOCCUED rowoccu[N];"IFOCCUED LeftTop_RightDown[2*N-1];"IFOCCUED RightTop_LefttDown[2*N-1];"ANSWER_TYPE answer[N];主程序
#include "eigqueprob.h""void nextline(int LineIndex){static asnnum = 0; "int RowIndex = 0; "int PrintIndex = 0;"for (RowIndex=0;RowIndex {"if ( ( notoccued == rowoccu[RowIndex] )\&&( notoccued == LeftTop_RightDown[LineIndex-RowIndex+N-1] )\&&( notoccued == RightTop_LefttDown[LineIndex+RowIndex] ) ){"rowoccu[RowIndex] = occued;LeftTop_RightDown[LineIndex-RowIndex+N-1] = occued;RightTop_LefttDown[LineIndex+RowIndex] = occued;"answer[LineIndex].line = LineIndex;answer[LineIndex].row = RowIndex;"if ( (N-1) > LineIndex ){nextline(LineIndex+1);}"else{asnnum++;printf("\nThe %dth answer is :",asnnum);for (PrintIndex=0;PrintIndex {printf("(%d,%d) ",answer[PrintIndex].line+1,answer[PrintIndex].row+1);}"if ((asnnum % 10) == 0)printf("\n\n");}"rowoccu[RowIndex] = notoccued;LeftTop_RightDown[LineIndex-RowIndex+N-1] = notoccued;RightTop_LefttDown[LineIndex+RowIndex] = notoccued;}}}main(){int i = 0;"nextline(i);"getchar();}C語言實現
回溯演算法
(a)為解決這個問題,我們把棋盤的橫坐標定為i,縱坐標定為j,i和j的取值範圍是從1到8。當某個皇后佔了位置(i,j)時,在這個位置的垂直方向、水平方向和斜線方向都不能再放其它皇后了。
用語句實現,可定義如下三個整型數組:a[8],b[15],c[24]。其中:
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++) "
if ((i,j)位置為空)) "
{佔用位置(i,j) "
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[3]={'0','0'};"int a[8],b[15],c[24],i;int h[8]={127,177,227,277,327,377,427,477};"int l[8]={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) "{a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;"putimage(h[i-1],l[j-1],arrow,COPY_PUT);"delay(500);"if(i<8) try(i+1);else "{n[1]++;if (n[1]>'9') {n[0]++;n[1]='0';}bar(260,300,390,340);"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<stdio.h>#include<memory.h>static int a[9][9],i,j,sum=0,t=1,column_status[9],slash_status[16],back_slash_status[17];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;}elseprintf("* ");}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;}}}}
易語言
.版本 2
.支持庫 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條右高左低的斜線上沒有皇后
' 左高右低數組[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 ; i count = count * size;}// 對每一個可能的情況for ( i=0 ; i // 計算這種情況下的棋盤上皇后的擺放位置,用 8 進位數表示// 此處可優化int temp = i;for ( j=0 ; j data [j] = temp % size;temp = temp / size;}// 測試這種情況是否可行,如果可以,輸出if ( test(data) )output( data );}}/** 測試這種情況皇后的排列是否可行**/public boolean test( int[] data ) {int i,j;for ( i=0 ; i for ( 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 ; i System.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;i placequeen(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 (i qsave[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;i if (qsave==false)continue;
if (num chess[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;i String row="第"+(i+1)+"行: ";
if (chess==0);
else
for(int j=0;j row+="++";
int j = chess;
while(j System.out.println(row);
}
}
}
//歷遍完成就停止
}
}
c#非遞歸實現
思路
採用的思路大致是這樣:
將一個皇後向下移動一個位置;
如果沒有成功移動(超出邊界),失敗;
如果成功移動,則判斷當前位置是否可用?如果不可用,則重做 1;
繼續給下一個皇后安排位置。
結束條件
如果第一個皇后的所有位置都嘗試完畢仍然沒有可用的解決方案或者最後一個皇后已經安排完畢。
代碼
1// AppEntry.cs
2using System;
3
4namespace Chenglin
5{
6 class AppEntry
7 {
8 static void Main(string[] args)
9 {
10 int queenNumber = 8;
11 QueenRowCollection q = new QueenRowCollection(queenNumber);
12
13 bool flag;
14 DateTime timeStarted = DateTime.Now;
15 flag = q.PositionQueens();
16 TimeSpan ts = DateTime.Now.Subtract( timeStarted );
17
18
19 if( flag ) {
20 Console.WriteLine( q.ToString() );
21 }
22 else {
23 Console.WriteLine( "Failed" );
24 }
25
26 Console.WriteLine( " seconds has been elapsed.", ts.TotalSeconds );
27 }
28 }
29} 1// QueenRowCollection.cs
2using System;
3using System.Text;
4
5namespace Chenglin
6{
7 public class QueenRowCollection
8 {
9
10 public QueenRowCollection( int numberOfQueens ){
11 this.numberOfQueens = numberOfQueens;
12 this.rows = new QueenRow[ numberOfQueens ];
13
14 for( int i=0;i 15 rows = new QueenRow( numberOfQueens );
16 }
17 }
18
19 public bool PositionQueens()
20 {
21 return PositionQueen( 0 );
22 }
23
24 private bool PositionQueen( int row )
25 {
26 if( row>=this.numberOfQueens ) {
27 return true;
28 }
29
30 QueenRow q = rows[row];
31 while( q.MoveNext() )
32 {
33 if( PositionAvailable( row, q.CurrentPosition ) ) {
34 // An available position has been found for the current queen,
35 // and try to find a proper position for the next queen.
36 //
37 // If no available position can be found for the next queen,
38 // the current queen should move to the next position and try again.
39 //
40 if( PositionQueen( row+1 ) )
41 {
42 // Both the current queen and the next queen
43 // have found available positions.
44 //
45 return true;
46 }
47 }
48 }
49
50 // No position is available for the current queen,
51 //
52 return false;
53 }
54
55 private bool PositionAvailable( int row, int column ){
56 for( int i=row-1; i>=0; i-- )
57 {
58 if( rows.PositionOccupied( column ) )
59 return false;
60
61 if( rows.PositionOccupied( column-(i-row) ) )
62 return false;
63
64 if( rows.PositionOccupied( column+(i-row) ) )
65 return false;
66 }
67
68 return true;
69 }
70
71 public override string ToString()
72 {
73 StringBuilder s = new StringBuilder();
74
75 foreach( QueenRow q in rows ){
76 s.AppendFormat( "", q, Environment.NewLine );
77 }
78
79 return s.ToString();
80 }
81
82 private int numberOfQueens;
83 private QueenRow [] rows;
84 }
85} 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 && currentPosition 18 columns[currentPosition] = false;
19 }
20
21 if( currentPosition 22 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<Position> allPositions = GetAllPositions(queens);
int column = 0;
List<List<Position>> solutions = newList<List<Position>>();
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<Position> CurrentPositions = newList<Position>();
List<KeyValuePair<int, List<Position>>> stack = newList<KeyValuePair<int, List<Position>>>();
publicvoid push(int i, List<Position> p )
{
stack.Add(newKeyValuePair<int, List<Position>>(i, p));
}
publicKeyValuePair<int, List<Position>> pop()
{
KeyValuePair<int, List<Position>> 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<KeyValuePair<int, List<Position>>> 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<bool, int> EightQueens(int queens, List<Position> allPositions, int column, Stack stack, List<List<Position>> solutions)
{
if (column == queens)
{
List<Position> newLst = newList<Position>();
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<Position>());
}
List<Position> results;
if (solutions.Count > 0)
{
results = solutions[solutions.Count - 1];
}
else
{
results = newList<Position>();
}
List<Position> newPositions = newList<Position>();
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[0].QueenNumber = column;
results.Add(newPositions[0]);
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<bool, int>(true, 0);
}
}
}
staticList<Position> GetAllPositions(int queens)
{
List<Position> positions = newList<Position>();
for (int i = 0; i < queens; i++)
{
for (int j = 0; j < queens; j++)
{
positions.Add(newPosition(i, j));
}
}
return positions;
}
staticList<Position> FilterPositions(List<Position> original, Position newPosition)
{
return original.FindAll(a => CheckPosition(a, newPosition));
}
staticList<Position> FilterPositions(List<Position> original, List<Position> newPositions)
{
if (newPositions == null || newPositions.Count == 0)
{
return original;
}
List<Position> ps = newList<Position>();
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<Position> positions)
{
for (int i = 0; i < positions.Count; i++)
{
Console.Write(positions[i].left);
Console.Write(positions[i].right + ",");
}
Console.WriteLine();
}
#endregion
}
C++實現
這裡介紹一個編程複雜度小,思路清晰的代碼
#include
using namespace std;
int width=8,lim=(1< void queen(int col,int ld,int rd) //分別是列,正斜線,反斜線,
{//col的二進位位中的1代表該行不能放的地方,ld,rd同理
if(col==lim){ans++;return;} //遞歸終止條件:col的二進位位在width(棋盤寬度)內都是1(放滿了)
int pos=lim&~(col|ld|rd); //col,ld,rd都是0的位可以放皇后,pos該位置1
while(pos)
{
int t=pos&-pos; //取pos最右邊的1位放皇后
pos-=t;
queen(col|t,(ld|t)<<1,(rd|t)>>1); //往棋盤的下一行遞歸,左斜線的限制往左,右斜線往右,可以畫圖看看
}
}
int main()
{
queen(0,0,0); //
cout< return 0;
}
C++另外一種方法:
#include<iostream>
using namespace std;
int a[8]; int b[8]; int c=0;
bool flag(int pos) {
int i;
for(i=0;i<pos;++i) {
if(a[i]==a[pos]) {return false;}
if(a[i]==a[pos]-(pos-i)||a[i]==a[pos+(pos-i)) {return false;}
}
return true;
}
void start(int pos) {
int i;
for(i=0;i<n;++i) {
a[pos]=i; if(flag(pos)) {
if(pos==7) {c++;}
else {start(pos+1);}
}}
return;}
int main() { int i,j;
for(i=0;i<n;i++) a[i]=-1;
start(0);
cout<<c<<"種方法";
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
作者:kkng09時間:2003-9-5 17:53
#/bin/bash
canSet() { # 檢查是否可放下皇后的子程序.
for ((n=0;n<y;n++)) ;do
((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個對稱位置,但是有些解經過對稱操作后和沒有操作前是一樣的。
八皇后問題
在一個標準的8x8的棋盤中,92個解當中有12個解是獨立的。8x8棋盤的獨立解如圖所示。
如果把棋盤從8X8變成NxN, 八皇后問題就變成了N皇后問題。N從4以上都有解,並分別有相應的獨立解。
下面是皇后的數目於解數目的關係
皇后數: 4 5 6 7 8 9 10 11 12 13 14
獨立解: 1 2 1 6 12 46 92 341 1787 9233 45752
全部解: 2,104,409,235,272,426,801,420,073,712,365,596
皇后數
4
5
6
7
8
9
10
11
12
13
14
獨立解
1
2
1
6
12
46
92
341
1787
9233
45752
全部解
2
10
4
40
92
352
724
2680
14200
73712
365596
比較特殊的是,皇后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實現
?'主要利用遞推思想 挨個判斷是否可放置皇后若是 繼續放置下一個 否則尋找其餘位置
'所需控制項 一個 list控制項 list1
'一個按鈕 command1
Dim int1 As Integer
Private Sub command1_click()
List1.Clear
int1 = 0
Dim i As Single, j As Single
i = 1
j = 1
Dim p As Integer, b As Boolean
Dim a(1 To 8, 1 To 8) As Boolean
Dim ii(1 To 8) As Single
Dim jj(1 To 8) As Single
a(i, j) = True
ii(1) = i
jj(1) = j
Do
Do While i < 8
i = i + 1
If i = 0 Then Exit Sub
j = 1
If b = True Then
a(i,jj(i)) = False
b = False
j = jj(i)+ 1
End If
Do
If j > 8 Then i =i - 2: b = True: Exit Do
For p = 1 To i - 1
Ifj = jj(p) Or Abs(i - ii(p)) = Abs(j - jj(p)) Then Exit For
Next
If p = i Then Exit Do
j = j + 1
Loop
If b = False Then
ii(i) = i: jj(i) = j
a(i, j) = True
End If
Loop
Dim p1 As Integer, p2 As Integer, str1 As String
For p1 = 1 To 8
str1 = ""
For p2 = 1 To 8
If a(p1,p2) = False Then
str1= str1 & "+ "
Else: str1= str1 & "@ "
End If
Next
List1.AddItem str1
Next
int1 = int1 + 1
Caption = int1
i = i - 1: b = True
List1.AddItem " "& Str(int1)
List1.AddItem vbCrLf
Loop
End Sub

八皇後圖

八皇後圖

相關評論

同義詞:暫無同義詞