八皇後問題演算法
Ⅰ 八皇後問題求解方法分類
八皇後問題
{
「八皇後」問題
遞歸法
求解
(
Pascal語言
)
八皇後問題是一個古老而著名的問題，是
回溯演算法
的典型例題。該問題是十九世紀著名的數學家
高斯
1850年提出：在8X8格的
國際象棋
上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。
高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，後來有人用
圖論
的方法解出92種結果。現代教學中，把八皇後問題當成一個經典
遞歸演算法
例題。
演算法分析
：數組a、b、c分別用來標記沖突，a數組代表列沖突，從a[0]~a[7]代表第0列到第7列，如果某列上已經有皇後，則為1，否則為0；
數組b代表主對角線沖突，為b[i-j+7]，即從b[0]~b[14]，如果某條主對角線上已經有皇後，則為1，否則為0；
數組c代表從對角線沖突，為c[i+j]，即從c[0]~c[14]，如果某條從對角線上已經有皇後，則為1，否則為0；
另優化：第一個皇後在1~4格，最後*2，即為總解數
}
program
queens;
var
a:array
[1..8]
of
integer;
b,c,d:array
[-7..16]
of
integer;
t,i,j,k:integer;
procere
print;
begin
t:=t+1;
write(t,':
');
for
k:=1
to
8
do
write(a[k],'
');
writeln;
end;
procere
try(i:integer);
var
j:integer;
begin
for
j:=1
to
8
do
{每個皇後都有8種可能位置}
if
(b[j]=0)
and
(c[i+j]=0)
and
(d[i-j]=0)
then
{判斷位置是否沖突}
begin
a:=j;
{擺放皇後}
b[j]:=1;
{宣布佔領第J行}
c[i+j]:=1;
{佔領兩個對角線}
d[i-j]:=1;
if
i<8
then
try(i+1)
{8個皇後沒有擺完，遞歸擺放下一皇後}
else
print;
{完成任務，列印結果}
b[j]:=0;
{回溯}
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
fillchar(a,sizeof(a),0);
{初始化數組}
fillchar(b,sizeof(b),0);
fillchar(c,sizeof(c),0);
fillchar(d,sizeof(d),0);
try(1);{從第1個皇後開始放置}
end.
「八皇後」問題遞歸法求解
(c語言)
＃i
nclude
"stdio.h"
static
char
Queen[8][8];
static
int
a[8];
static
int
b[15];
static
int
c[15];
static
int
iQueenNum=0;
//記錄總的棋盤狀態數
void
qu(int
i);
//參數i代錶行
int
main()
{
int
iLine,iColumn;
//棋盤初始化，空格為*，放置皇後的地方為@
for(iLine=0;iLine<8;iLine++)
{
a[iLine]=0;
//列標記初始化，表示無列沖突
for(iColumn=0;iColumn<8;iColumn++)
Queen[iLine][iColumn]='*';
}
//主、從對角線標記初始化，表示沒有沖突
for(iLine=0;iLine<15;iLine++)
b[iLine]=c[iLine]=0;
qu(0);
return
0;
}
void
qu(int
i)
{
int
iColumn;
for(iColumn=0;iColumn<8;iColumn++)
{
if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0)
//如果無沖突
{
Queen[iColumn]='@';
//放皇後
a[iColumn]=1;
//標記，下一次該列上不能放皇後
b[i-iColumn+7]=1;
//標記，下一次該主對角線上不能放皇後
c[i+iColumn]=1;
//標記，下一次該從對角線上不能放皇後
if(i<7)
qu(i+1);
//如果行還沒有遍歷完，進入下一行
else
//否則輸出
{
//輸出棋盤狀態
int
iLine,iColumn;
printf("第%d種狀態為：\n",++iQueenNum);
for(iLine=0;iLine<8;iLine++)
{
for(iColumn=0;iColumn<8;iColumn++)
printf("%c
",Queen[iLine][iColumn]);
printf("\n"screen.width/2)this.width=screen.width/2"
vspace=2
border=0>;
}
printf("\n\n"screen.width/2)this.width=screen.width/2"
vspace=2
border=0>;
}
//如果前次的皇後放置導致後面的放置無論如何都不能滿足要求，則回溯，重置
Queen[iColumn]='*';
a[iColumn]=0;
b[i-iColumn+7]=0;
c[i+iColumn]=0;
}
}
}
八皇後的c語言解法：
#include
<stdio.h>
#include
<conio.h>
#include
<math.h>
int
n,k,a[20],num=0;
int
attack(int
k){
int
flag=0;
int
i=1;
while
((i<k)&&(a[k]!=a)&&(fabs(a[k]-a)!=(k-i)))
i++;
if
(i==k)
flag=1;
return
flag;
}
void
place(int
k)
{
//printf("
%d",k);
int
i;
if
(k==n+1){
num=num+1;
printf("num=%d:",num);
for
(i=1;i<n+1;i++)
printf("
%d",a);
printf("\n");}
else
{
for
(i=1;i<n+1;i++){
a[k]=i;
if
(attack(k)==1)
place(k+1);
else
a[k]=0;
}
}
}
main(){
scanf("%d",&n);
k=1;
place(k);
if
(k!=n+1)
printf("no
solution!\n");
getch();
}
n皇後問題（英文）http://mathworld.wolfram.com/QueensProblem.html
Ⅱ 如何用C語言編寫八皇後問題
#include "stdio.h" x0dx0a#include "windows.h" x0dx0a#define N 8 /* 定義棋盤大小 */ x0dx0aint place(int k); /* 確定某一位置皇後放置與否，放置則返回1，反之返回0 */ x0dx0avoid backtrack(int i);/* 主遞歸函數，搜索解空間中第i層子樹 */ x0dx0avoid chessboard(); /* 每找到一個解,列印當前棋盤狀態 */ x0dx0astatic int sum, /* 當前已找到解的個數 */ x0dx0ax[N]; /* 記錄皇後的位置,x[i]表示皇後i放在棋盤的第i行的第x[i]列 */ x0dx0aint main(void) x0dx0a{ x0dx0abacktrack(0); x0dx0asystem("pause"); x0dx0areturn 0; x0dx0a} x0dx0aint place(int k) x0dx0a{ x0dx0a/* 測試皇後k在第k行第x[k]列時是否與前面已放置好的皇後相攻擊。 x[j] == */ x0dx0a/* x[k] 時，兩皇後在同一列上；abs(k - j) == abs(x[j] - x[k]) 時，兩皇 */ x0dx0a/* 後在同一斜線上。兩種情況兩皇後都可相互攻擊，故返回0表示不符合條件。*/ x0dx0afor (int j = 0; j < k; j ++) x0dx0aif (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k])) return 0; x0dx0areturn 1; x0dx0a} x0dx0avoid backtrack(int t) x0dx0a{ x0dx0a/* t == N 時，演算法搜索至葉結點，得到一個新的N皇後互不攻擊的放置方案 */ x0dx0aif (t == N) chessboard(); x0dx0aelse x0dx0afor (int i = 0; i < N; i ++) { x0dx0ax[t] = i; x0dx0aif (place(t)) backtrack(t + 1); x0dx0a} x0dx0a} x0dx0avoid chessboard() x0dx0a{ x0dx0aprintf("第%d種解法:\n", ++ sum); x0dx0afor (int i = 0; i < N; i ++) { x0dx0afor (int j = 0; j < N; j ++) x0dx0aif (j == x[i]) printf("@ "); x0dx0aelse printf("* "); x0dx0aprintf("\n"); x0dx0a} x0dx0aprintf("\n"); x0dx0a}
Ⅲ 暴力窮舉和回溯法（八皇後問題）
以前每次遇到演算法問題都是直接暴力求解，一直以為自己用的是暴力窮舉法，現在學了回溯法，發現部分問題其實使用的是回溯法，而不是單純的暴力窮舉。
例如求解一個n皇後問題：
1.使用暴力窮舉，由於沒有兩個皇後能夠放在一列上，那麼解向量一定是數1，2，····，n的一個排列（第一行n種放法，第二行n-1種，以此類推）。時間復雜度O(n!).
為什麼是一維而不是兩維？因為沒有兩個皇後能在同一列，所以只用行標志就可以表示出皇後的位置，簡化了問題
2.回溯法，就等於是一個一個的試，從1到n，時間復雜度O(n^n),每一行n種放法，總共n行。
看起來回溯法要比暴力窮舉差很多，但是實際上回溯法很多時候實際演算法復雜度並沒有暴力窮舉高。比如4皇後問題中，僅需要341個可能節點中的27個節點就可以找到解，但是暴力窮舉實際會慢很多。
換一個思路，比如第一個皇後放在了0位置，暴力窮舉第二個皇後放在1位置，那麼之後的皇後無論怎麼放都是錯誤的，也就是(n-2)!個向量全部都是錯誤的，而回溯法面對這種問題，會在之前就直接拋棄這種情況，速度會快很多。不要問為什麼暴力窮舉為什麼不學回溯法那樣提前拋棄，因為它是 暴力窮舉 （這還算優化過一次，不然直接O(n^n)）。
總而言之，回溯法並不需要得到所有情況，而且運行過程中會提前拋棄不合要求的情況，所以演算法復雜度一般不會到最差的情況。
Ⅳ 八皇後究竟有多少種解法怎麼解
八皇後問題是一個古老而著名的問題，是回溯演算法的典型例題。該問題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線慶段上，問有多少種擺法。 高斯認為有76種方案。1854年在柏林的象譽頌譽棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。 對於八皇後問題的實現，如果結合動態的圖形演示，則可以使演算法的描述櫻猜更形象、更生動，使教學能產生良好的效果。下面是用Turbo C實現的八皇後問題的圖形程序，能夠演示全部的92組解。八皇後問題動態圖形的實現
Ⅳ 八皇後問題演算法詳解
八皇後問題，是一個古老而著名的問題，是 回溯演算法 的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾於1848年提出：在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。 高斯 認為有76種方案。1854年在柏林的擾游象棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。
本文緩帆銷的主要描述的是基於回溯演算法轎備思想的求解演算法，並盡可能在細節上給予讀者直觀展示，以使得讀者可以有更好的理解。拋磚引玉，如有錯誤請不吝賜教。
演算法的關鍵在於用一個二維數組chess [ ] [ ] 來記錄每一個位置(第 i 行第 j 列)是否合法（行列對角線上沒有填皇後，對應於數組 chess [ i ] [ j ] 為 0），用一個一維數Queenplace [ ] 組來記錄每一行上皇後的列標（比如Queenplace [ row ] =column 表示第 row 行第 column 列填入皇後）。
行數 i 從第一行開始，遍歷每一列 j ，如果chess [ i ] [ j ] 為0，那麼說明此位置可以填入皇後，則將chess中與此位置同行同列同對角線的value自增 1 並且在 數組Queenplace 中記錄相應的坐標。然後遞歸計算每一行直到最後一行成功填入皇後並在此時列印棋盤 。最後進行回溯，恢復chess [ ] [ ] ，將chess中與此位置同行同列同對角線的value自減 1 並繼續進行下一列的計算。