n皇後演算法

㈠ 八皇後問題是什麼問題呀

這就是著名的八皇後問題。八個皇後在排列時不能同在一行、一列或一條斜
線上。在8!=40320種排列中共有92種解決方案。

「八皇後」動態圖形的實現

八皇後問題是一個古老而著名的問題，是回溯演算法的典型例題。該問題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。
高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。
對於八皇後問題的實現，如果結合動態的圖形演示，則可以使演算法的描述更形象、更生動，使教學能產生良好的效果。下面是筆者用Turbo C實現的八皇後問題的圖形程序，能夠演示全部的92組解。八皇後問題動態圖形的實現，主要應解決以下兩個問題。

1．回溯演算法的實現
（1）為解決這個問題，我們把棋盤的橫坐標定為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)的對角岩備租線（右上至左下）有皇後

（2）為第i個皇後選擇位置的演算法如下：

for(j=1;j<=8;j++) /*第i個皇後在第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,)將點陣圖置於屏幕上以（x，y）左上角的區域。

3． 程序清單如下

＃i nclude <graphics.h>
＃i nclude <stdlib.h>
＃i nclude <stdio.h>
＃i nclude <dos.h>
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[i]=1;
for (i=0;i<=14;i++) b[i]=1;
for (i=0;i<=23;i++) c[i]=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);
}

八皇後問題的串列演算法

1 八皇後問題

所謂八皇後問題,是在8*8格的棋盤上,放置8個皇後。要求每行每列放一個皇後,而且每一條對角線和每一條反對角線上不能有多於1個皇後,也即對同時放置在棋盤的兩個皇後(row1,column1)和(row2,column2),不允許(column1-column2)=(row1-row2)或者(column1+row1)=(column2+row2)的情況出現。

2 八皇後問題的串列遞歸演算法

八皇後問題最簡單的串列解法為如下的遞歸演算法:

(2.1)深度遞歸函數:

go(int step,int column)

{int i,j,place;

row[step]=column;

if (step==8)

outputresult( ); /*結束遞歸列印結果*/

else /*繼續遞歸*/

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

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

if(collision(j ,row[j],step+1,place))

/*判斷是否有列沖突、對角線或反對角線*/

goto skip_this_place;

go(step+1,place);

skip_this_place:;

}

}

}/* go */

(2.2)主函數:

void main( )

{int place,j;

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

go(1,place);

}/* main */

八皇後問題的並行演算法

該演算法是將八皇後所有可能的解放在相應的棋盤上,主進程負責生成初始化的棋盤，並將該棋盤發送到某個空閑的子進程,由該子進程求出該棋盤上滿足初始化條件的所有的解。這里，我們假定主進程只初始化棋盤的前兩列，即在棋盤的前兩列分別放上2個皇後,這樣就可以產生8*8=64個棋盤。

1 主進程演算法

主進程等待所有的子進程,每當一個子進程空閑的時侯，就向主進程發送一個Ready(就緒)信號。主進程收到子進程的Ready信號後,就向該子進程發送一個棋盤。當主進程生成了所有的棋盤後,等待所有的子進程完成它們的工作。然後向每個子進程發送一個Finished信號,列印出各個子進程找到的解的總和，並退出。子進程接收到Finished信號也退出。

2 子進程演算法

每個子進程在收到主進程發送過來的棋盤後,對該棋盤進行檢查。若不合法,則放棄該棋盤。子進程回到空閑狀態,然後向主進程發送Ready信號,申請新的棋盤;若合法,則調用move_to_right(board,rowi,colj)尋找在該棋盤上剩下的6個皇後可以擺放的所有位置,move_to_right(board,rowi,colj)是個遞歸過程, 驗證是否能在colj列rowi行以後的位置是否能放一個皇後。

1)首先將more_queen設置成FALSE；

以LEAF,TRUE和FLASE區分以下三種情況:

A)LEAF:成功放置但是已到邊緣,colj現在已經比列的最大值大1,回退兩列,檢查是否能將待檢查皇後放在哪一行:如果能,把more_queen設成TRUE;

B)TRUE:成功放置皇後,檢查這一列是否能有放置皇後的其他方式,如有,把more_queen設成TRUE;

C)FALSE:不能放置,回退一列再試,如果能把more_queen設成TRUE ,如果皇後已在最後一行,必須再檢查上一列。

2)如果more_queens=TRUE,仍需再次調用move_to_right(),為新棋盤分配空間,用xfer()將現有棋盤拷貝到nextboard，並進行下列情況的處理：

TRUE:得到一個皇後的位置,增大列數再試；

FALSE:失敗,如果more_queen為真, 取回棋盤,保存上次調用的棋盤。將列數減小,取走皇後,增加行數,再調用move_to_right()；

LEAF:得到一種解法,solution增一,將解法寫入log_file,由於已到邊緣,列數回退1,檢查是否放置一個皇後,如果能,新加一個皇後後,調用move_to_right；如果不能,檢查more_queen如果more_queen為真,將棋盤恢復到上次調用時保存的棋盤,將待檢查的皇後下移,調用move_to_right。

八皇後問題的高效解法-遞歸版

// Yifi 2003 have fun! : )

//8 Queen 遞歸演算法
//如果有一個Q 為 chess[i]=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<QueenMax;i++)chess[i]=-1;
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<QueenMax;i++) qsave[i]=true;

//下面先把安全位數組完成
i=0;//i 是現在要檢查的數組值
while (i<num){
qsave[chess[i]]=false;
int k=num-i;
if ( (chess[i]+k >= 0) && (chess[i]+k < QueenMax) ) qsave[chess[i]+k]=false;
if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) qsave[chess[i]-k]=false;
i++;
}
//下面歷遍安全位
for(i=0;i<QueenMax;i++){
if (qsave[i]==false)continue;
if (num<QueenMax-1){
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<QueenMax;i++){
String row="第"+(i+1)+"行: ";
if (chess[i]==0);
else
for(int j=0;j<chess[i];j++) row+="--";
row+="++";
int j = chess[i];
while(j<QueenMax-1){row+="--";j++;}
System.out.println(row);
}
}
}
//歷遍完成就停止

㈡ 用回溯法解定和子集問題、0/1背包問題和n皇後問題的演算法比較

我只寫了一個n皇後的解法，其它的沒寫，不知道什麼意思。程序如下：
#include <iostream>
using namespace std;
#define MAX 5 //數組維數
static int total=0; //演算法總數
int array[MAX][MAX]; //定義數組
void SetArray() //數組置零
{
int i,j;
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
array[i][j]=0;
}
bool IsTrue(int a,int b) //合法性判斷
{
int i,j,len;
for (i=0;i<MAX;i++)
if(array[a][i]==1||array[i][b]==1)
return false;
len=(a<b?a:b);
for(i=a-len,j=b-len;i<MAX&&j<MAX;i++,j++)
if(array[i][j]==1)
return false;
for(i=a,j=b;i<MAX&&j>=0;i++,j--)
if(array[i][j]==1)
return false;
for(i=a,j=b;i>=0&&j<MAX;i--,j++)
if(array[i][j]==1)
return false;
return true;
}
void show() //顯示結果
{
int i,j;
cout<<"第"<<++total<<"種結果為："<<endl;
for (i=0;i<MAX;i++)
{
for(j=0;j<MAX;j++)
cout<<array[i][j]<<" ";
cout<<endl;
}

}
bool Queen(int i) //皇後演算法
{
int j;
for(j=0;j<MAX;j++)
{
if(IsTrue(i,j))
{
array[i][j]=1;
if(i==MAX-1)
{
show();
array[i][j]=0;
continue;
}
else if(!Queen(i+1))
{
array[i][j]=0;
continue;
}
}
}
return false;
}
void main()
{
int i;
for(i=0;i<MAX;i++)
{
SetArray();
array[0][i]=1;
Queen(1);
}
}
不明白的可以來問我。。

㈢ 演演算法的n 皇後問題是否必然有解，理由是什麼 研究好久到處爬文還是搞不太懂QAQ 謝謝！！

N皇後問題是一個經典的問題，在一個N*N的棋盤上放置N個皇後，每行一個並使其不能互相攻擊（同一行、同一列、同一斜線上的皇後都會自動攻擊）。

一、 求解N皇後問題是演算法中回溯法應用的一個經典案例
回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。
在現實中，有很多問題往往需要我們把其所有可能窮舉出來，然後從中找出滿足某種要求的可能或最優的情況，從而得到整個問題的解。回溯演算法就是解決這種問題的「通用演算法」，有「萬能演算法」之稱。N皇後問題在N增大時就是這樣一個解空間很大的問題，所以比較適合用這種方法求解。這也是N皇後問題的傳統解法，很經典。

下面是演算法的高級偽碼描述，這里用一個N*N的矩陣來存儲棋盤：
1) 演算法開始, 清空棋盤，當前行設為第一行，當前列設為第一列
2) 在當前行，當前列的位置上判斷是否滿足條件(即保證經過這一點的行,列與斜線上都沒有兩個皇後)，若不滿足，跳到第4步
3) 在當前位置上滿足條件的情形：
在當前位置放一個皇後，若當前行是最後一行，記錄一個解；
若當前行不是最後一行，當前行設為下一行, 當前列設為當前行的第一個待測位置；
若當前行是最後一行，當前列不是最後一列，當前列設為下一列；
若當前行是最後一行，當前列是最後一列，回溯，即清空當前行及以下各行的棋盤，然後，當前行設為上一行，當前列設為當前行的下一個待測位置；
以上返回到第2步
4) 在當前位置上不滿足條件的情形：
若當前列不是最後一列，當前列設為下一列，返回到第2步;
若當前列是最後一列了，回溯，即，若當前行已經是第一行了，演算法退出，否則，清空當前行及以下各行的棋盤，然後，當前行設為上一行，當前列設為當前行的下一個待測位置，返回到第2步;
演算法的基本原理是上面這個樣子，但不同的是用的數據結構不同，檢查某個位置是否滿足條件的方法也不同。為了提高效率，有各種優化策略，如多線程，多分配內存表示棋盤等。
在具體解決該問題時，可以將其拆分為幾個小問題。首先就是在棋盤上如何判斷兩個皇後是否能夠相互攻擊，在最初接觸這個問題時，首先想到的方法就是把棋盤存儲為一個二維數組，然後在需要在第i行第j列放置皇後時，根據問題的描述，首先判斷是在第i行是否有皇後，由於每行只有一個皇後，這個判斷也可以省略，然後判斷第j列是否有皇後，這個也很簡單，最後需要判斷在同一斜線上是否有皇後，按照該方法需要判斷兩次，正對角線方向和負對角線方向，總體來說也不難。但是寫完之後，總感覺很笨，因為在N皇後問題中這個函數的使用次數太多了，而這樣做效率較差，個人感覺很不爽。上網查看了別人的實現之後大吃一驚，大牛們都是使用一個一維數組來存儲棋盤，在某個位置上是否有皇後可以相互攻擊的判斷也很簡單。具體細節如下：

把棋盤存儲為一個N維數組a[N]，數組中第i個元素的值代表第i行的皇後位置，這樣便可以把問題的空間規模壓縮為一維O(N)，在判斷是否沖突時也很簡單，首先每行只有一個皇後，且在數組中只佔據一個元素的位置，行沖突就不存在了，其次是列沖突，判斷一下是否有a[i]與當前要放置皇後的列j相等即可。至於斜線沖突，通過觀察可以發現所有在斜線上沖突的皇後的位置都有規律即它們所在的行列互減的絕對值相等，即| row – i | = | col – a[i] | 。這樣某個位置是否可以放置皇後的問題已經解決。

㈣ 常見演算法思想6：回溯法

回溯法也叫試探法，試探的處事方式比較委婉，它先暫時放棄關於問題規模大小的限制，並將問題的候選解按某種順序逐一進行枚舉和檢驗。當發現當前候選解不可能是正確的解時，就選擇下一個候選解。如果當前候選解除了不滿足問題規模要求外能夠滿足所有其他要求時，則繼續擴大當前候選解的規模，並繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在試探演算法中，放棄當前候選解，並繼續尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。

（1）針對所給問題，定義問題的解空間。
（2）確定易於搜索的解空間結構。
（3）以深度優先方式搜索解空間，並在搜索過程中用剪枝函數避免無效搜索。

回溯法為了求得問題的正確解，會先委婉地試探某一種可能的情況。在進行試探的過程中，一旦發現原來選擇的假設情況是不正確的，馬上會自覺地退回一步重新選擇，然後繼續向前試探，如此這般反復進行，直至得到解或證明無解時才死心。

下面是回溯的3個要素。
（1）解空間：表示要解決問題的范圍，不知道範圍的搜索是不可能找到結果的。
（2）約束條件：包括隱性的和顯性的，題目中的要求以及題目描述隱含的約束條件，是搜索有解的保證。
（3）狀態樹：是構造深搜過程的依據，整個搜索以此樹展開。

下面是影響演算法效率的因素：

回溯法搜索解空間時，通常採用兩種策略避免無效搜索，提高回溯的搜索效率:

為縮小規模，我們用顯示的國際象棋8*8的八皇後來分析。按照國際象棋的規則，皇後的攻擊方式是橫，豎和斜向。
皇後可以攻擊到同一列所有其它棋子，因此可推導出每1列只能存在1個皇後，即每個皇後分別占據一列。棋盤一共8列，剛好放置8個皇後。

為了擺放出滿足條件的8個皇後的布局，可以按如下方式逐步操作：

把規模放大到N行N列也一樣，下面用回溯法解決N皇後問題：

執行：