八皇后問題

八皇后問題

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

  • 中文名稱
    八皇后
  • 外文名稱
    Eight queens
  • 類    別
    問題
  • 時    間
    1848年

​介紹

八皇后問題是一個以西洋棋為背景的問題:如何能夠在 8×8 的西洋棋棋盤上放置八個皇后,使得任何一個皇后都無法直接吃掉其他的皇后?為了達到此目的,任兩個皇后都不能處於同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的n皇后擺放問題:這時棋盤的大小變為n×n,而皇后個數也變成n。若且唯若 n = 1 或 n ≥ 4 時問題有解。

八皇后問題最早是由國際西洋棋棋手馬克斯·貝瑟爾於1848年提出。之後陸續有數學家對其進行研究,其中包括高斯和康托,並且將其推廣為更一般的n皇后擺放問題。八皇后問題的第一個解是在1850年由弗朗茲·諾克給出的。諾克也是首先將問題推廣到更一般的n皇后擺放問題的人之一。1874年,S.岡德爾提出了一個通過行列式來求解的方法,這個方法後來又被J.W.L.格萊舍加以改進。

艾茲格·迪傑斯特拉在1972年用這個問題為例來說明他所謂結構性編程的能力。

八皇后問題出現在1990年代初期的著名電子遊戲第七訪客中。

算法

問題

“殘卷法”思想

設定一個三維數組,第一個下標是皇后的行坐標,第二個下標是皇后的列坐標,第三個下標是殘卷號。相當於有N張疊在一起的8*8棋盤,每張棋盤只在複製前面棋盤及皇后後加放置一個皇后。直到放滿8皇后後才是一張完整的8皇后圖,稱完卷。

這裡實際操作時多加一行多加一列即第0行第0列,但這一行/列不作輸出,只是作此行/列有無皇后的參考。

代碼

#include "stdio.h"

void main()

{static int a[9][10][1645],x,y,i,j,z=1,k,flag,h,m,n=0;

for(k=1;k<=z;k++)

{for(x=1;x<=8;x++)

{if(x==8 && m==0) {flag=z+1;m=1;}//殘卷算到了第8行,表明已經是完卷。即完卷從l號殘卷開始的。

if(a[x][0][k]==2) continue;//參考行等於2則表明此行己有皇后,下一行

for(y=1;y<=8;y++)

{if(a[0][y][k]==2) continue;//參考列等於2則表明此列己有皇后,下一列

if(x>1) if(a[x-1][y-1][k]==1||a[x-1][y+1][k]==1) continue;//左右對角線有皇后,下一列

if(x>2) if(a[x-2][y-2][k]==1||a[x-2][y+2][k]==1) continue;

if(x>3) if(a[x-3][y-3][k]==1||a[x-3][y+3][k]==1) continue;

if(x>4) if(a[x-4][y-4][k]==1||a[x-4][y+4][k]==1) continue;

if(x>5) if(a[x-5][y-5][k]==1||a[x-5][y+5][k]==1) continue;

if(x>6) if(a[x-6][y-6][k]==1||a[x-6][y+6][k]==1) continue;

if(x>7) if(a[x-7][y-7][k]==1||a[x-7][y+7][k]==1) continue;

for(i=0;i<9;i++)

for(j=0;j<9;j++)

a[j][z+1]=a[j][k];//複製當前殘卷內容

a[x][y][z+1]=1;//放置一個皇后到新殘卷

a[0][y][z+1]=2;//設定參考列為2,表明此列有皇后

a[x][0][z+1]=2;//設定參考行為2,表明此行有皇后

z++;//取下一個殘卷號

}

break; }

for(k=flag;k<=z;k++)

{//輸出8皇后

for(i=1;i<=8;i++)

{for(j=1;j<=8;j++)

printf("%d ",a[j][k]);

printf(" ");

for(j=1;j<=8;j++)

printf("%d ",a[9-j][k]);//將上圖順時針鏇轉90度得到新圖

printf(" ");

for(j=1;j<=8;j++)

printf("%d ",a[9-i][9-j][k]);//將上圖順時針鏇轉90度得到新圖

printf(" ");

for(j=1;j<=8;j++)

printf("%d ",a[j][9-i][k]);//將上圖順時針鏇轉90度得到新圖

printf(" ");

printf("\n");

}

printf("\n");

n++;if(n%4==0) getchar();

}

printf("總共%d種 Hyber-bin製作",n*4);//輸出總共有多少種

}

解法

我是深搜的,有一點值得注意,顯然,八皇后問題每行必須有一個皇后,所以,對棋盤深搜時,第一個皇后的位置不妨設為第一行,這樣只對第一行進行搜尋,同理,第二個皇后不妨設為第二行,以此類推。這就是我下面代碼中深搜只有一個for循環的原因,不這么思考,總會有不小心多次輸出同一結果的情形。

下面附我的代碼:

#include<iostream>

using namespace std;

struct node1

{bool b[8][8]; };//棋盤模擬,不可以放皇后的地方值為0,可以為1;

struct node2

{ int x,y;};//記錄放皇后的位置坐標

//node1 a[9];

node1 visited[9];

node2 zb[8];

int num;//記錄有多少中方法

void print()//輸出用的函式,坐標從0開始,到7/。

{printf("case%d: ",++num); for(int i=0;i<=7;i++)

{printf("%d,%d\t",zb.x,zb.y); }

cout<<'\n';

}

int x1,x2,x3,x4,y1,y2,y3,y4;

void vis(int x,int y,int step)//模擬記錄在第step步時,把皇后放在x,y位置後,哪些地方就不能放皇后了。

{

x1=x;y1=y;

x2=x;y2=y;

x3=x;y3=y;

x4=x;y4=y;

visited[step]=visited[step-1];

for(int i=0;i<8;i++)

{

visited[step].b[x]=0;

visited[step].b[y]=0;

}

while(x1<8&&y1<8)

{

visited[step].b[x1][y1]=0;

x1++;y1++;

}

while(x4<8&&y4>=0)

{

visited[step].b[x4][y4]=0;

x4++;y4--;

}

}

void DFS(int step)

{

if(step==9)//step=9時,說明已經放了八個皇后了,該是輸出的時候了。

print();

else

{

for(int j=0;j<8;j++)

if(visited[step-1].b[step-1][j])

{

zb[step-1].x=step-1;

zb[step-1].y=j;

vis(step-1,j,step);

DFS(step+1);

}

}

}

int main()

{

num=0;

memset(visited,1,sizeof(visited));

DFS(1);

//cout<<"hello world"<<endl;

system("pause");

}

相關

-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).

例子

檔案

eigqueprob.h

#include

#define N 8 /* N 表示皇后的個數 */

/* 用來定義答案的結構體 */

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);

}

/* 每10個答案一組,與其他組隔兩行 */

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();

}

帶圖形顯示的實現

對於八皇后問題的實現,如果結合動態的圖形演示,則可以使算法的描述更形象、更生動,使教學能產生良好的效果。下面是用Turbo C實現的八皇后問題的圖形程式,能夠演示全部的92組解。八皇后問題動態圖形的實現,主要應解決以下兩個問題。

(1)回溯算法的實現

(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++) /*第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

#include

char 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) /*如果第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[1]++;if (n[1]>'9') {n[0]++;n[1]='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);

}

語言

.版本 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個數組模擬棋盤上皇后的位置

' 皇后位置數組[j]=4,表示第j列,第皇后位置數組[j]行有皇后

' 引入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

.判斷循環尾 ()

返回 (結果控制變數) ' 返回最終是否有解的信息

舉例

#include "stdio.h"

#include "windows.h"

#define N 8 /* 定義棋盤大小 */

int place(int k); /* 確定某一位置皇后放置與否,放置則返回1,反之返回0 */

void backtrack(int i);/* 主遞歸函式,搜尋解空間中第i層子樹 */

void chessboard(); /* 每找到一個解,列印當前棋盤狀態 */

static int sum, /* 當前已找到解的個數 */

x[N]; /* 記錄皇后的位置,x表示皇后i放在棋盤的第i行的第x列 */

int main(void)

{

backtrack(0);

system("pause");

return 0;

}

int place(int k)

{

/* 測試皇后k在第k行第x[k]列時是否與前面已放置好的皇后相攻擊。 x[j] == */

/* x[k] 時,兩皇后在同一列上;abs(k - j) == abs(x[j] - x[k]) 時,兩皇 */

/* 後在同一斜線上。兩種情況兩皇后都可相互攻擊,故返回0表示不符合條件。*/

for (int j = 0; j < k; j ++)

if (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k])) return 0;

return 1;

}

void backtrack(int t)

{

/* t == N 時,算法搜尋至葉結點,得到一個新的N皇后互不攻擊的放置方案 */

if (t == N) chessboard();

else

for (int i = 0; i < N; i ++) {

x[t] = i;

if (place(t)) backtrack(t + 1);

}

}

void chessboard()

{

printf("第%d種解法:\n", ++ sum);

for (int i = 0; i < N; i ++) {

for (int j = 0; j < N; j ++)

if (j == x) printf("@ ");

else printf("* ");

printf("\n");

}

printf("\n");

}

實現

#include

#define q(o) a[j]o[j+i+7]o[j-i+31]

int a[39];

void main(int i,int j)

{

for(j=9;--j;i>8?printf("%10d ",a[j]):q(|a)||(q(=a)=i,main(i+1,j),q(=a)=0));

}

循環

數據表示

* 用一個 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 );

}

}

方案

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);

}

}

}

//歷遍完成就停止

}

}

非遞歸實現

思路

採用的思路大致是這樣:

將一個皇后向下移動一個位置;

如果沒有成功移動(超出邊界),失敗;

如果成功移動,則判斷當前位置是否可用?如果不可用,則重做 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);

}

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]);

}

}

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.left);

Console.Write(positions.right + ",");

}

Console.WriteLine();

}

#endregion

}

編程

這裡介紹一個編程複雜度小,思路清晰的代碼

#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==a[pos]) {return false;}

if(a==a[pos]-(pos-i)||a==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=-1;

start(0);

cout<<c<<"種方法";

system("pause");

return 0;

}

Python

from itertools import permutations

n = 8

cols = range(n)

for vec in permutations(cols):

if (n == len(set(vec+i for i in cols))

== len(set(vec-i for i in cols))):

print vec

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代表行,ans代表列;

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:=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 10 4 40 92 352 724 2680 14200 73712 365596

皇后數4567891011121314
獨立解12161246923411787923345752
全部解2104409235272426801420073712365596

比較特殊的是,皇后6x6棋盤的解比5x5少,其餘解的數目隨著皇后數目增加。但似乎無數學表達式可以描述。

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

八皇后問題

相關詞條

其它詞條