回溯演算法八皇後

A. 用遞歸函數設計八皇後問題的回溯演算法C++代碼

解析：遞歸實現n皇後問題。
演算法分析：
數組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。
代碼如下：
#include <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[i][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");
}
printf("\n\n");
}
//如果前次的皇後放置導致後面的放置無論如何都不能滿足要求，則回溯，重置
Queen[i][iColumn]='*';
a[iColumn]=0;
b[i-iColumn+7]=0;
c[i+iColumn]=0;
}
}
}

B. c語言八皇後的問題。 需要代碼，外加步驟解釋。謝謝

#include
<stdlib.h>
#include
<stdio.h>
int
m[8][8]
=
{0};//表示棋盤，初始為0，表示未放置皇後
int
num
=
0;//解數目
//對於棋盤前row-1行已放置好皇後
//檢查在第row行、第column列放置一枚皇後是否可行
bool
check(int
row,int
column)
//
1,1
2,1
2,2
2,3
{
if(row==1)
return
true;
int
i,j;
//縱向只能有一枚皇後
for(i=0;i<=row-2;i++)
{
if(m[i][column-1]==1)
return
false;
}
//左上至右下只能有一枚皇後

//
i
=
row-2;
//
j
=
i-(row-column);

//
row
-
2
-
row
+
column
i
=
row
-
2;
j
=
column
-
2;
while(i>=0&&j>=0)
{
if(m[i][j]==1)
return
false;
i--;
j--;
}
//右上至左下只能有一枚皇後
i
=
row-2;
//
j
=
row+column-i-2;
j
=
column;
while(i>=0&&j<=7)
{
if(m[i][j]==1)
return
false;
i--;
j++;
//當已放置8枚皇後，為
}
return
true;
}
//可行解時，輸出棋盤
void
output()
{
int
i,j;
num++;
printf("answer
%d:
",num);
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
printf("%d
",m[i][j]);
printf("
");
}
}
//採用遞歸函數實現八皇後回溯演算法
//該函數求解當棋盤前row-1行已放置好皇後，在第row行放置皇後
void
solve(int
row)
{
int
j;
//考慮在第row行的各列放置皇後
for
(j=0;j<8;j++)
{
//在其中一列放置皇後
m[row-1][j]
=
1;

//
1,0
//檢查在該列放置皇後是否可行
if
(check(row,j+1)==true)
{
//若該列可放置皇後，且該列為最後一列，則找到一可行解，輸出
if(row==8)
output();
//若該列可放置皇後，則向下一行，繼續搜索、求解
else
solve(row+1);
}
//取出該列的皇後，進行回溯，在其他列放置皇後
m[row-1][j]
=
0;
}
}
//主函數
int
main()
{
//求解八皇後問題
solve(1);
return
0;
}
/*
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
0
6
0
0
0
0
0
0
0
0
7
0
0
0
0
0
0
0
0

*/

C. js版本的八皇後回溯演算法結果有誤

八皇後問題
八皇後問題，是一個古老而著名的問題，是回溯演算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾於1848年提出：在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。

工作原理
首先從定義知道，兩個皇後都不能處於同一行，所以第0個皇後放在第0行，第一個皇後放在第1行，以此類推。

先在第0行第0個格子（0,0）放一個皇後0，接著把處於同一行、同一列或同一斜線上的格子都標記為皇後0；

然後把皇後1放到第1行標記為-1的格子中，以此類推直到放下皇後7（即最後一個皇後）。

若中途出現放皇後 iQueen時，第 iQueen行所有格子已經被全部標記，即if( arr[ iQueen*n + i ].index == -1 )的判斷，則回溯到上一層函數（其實就是沒有進入到if分支，所有沒有進行遞歸了，代碼執行完自然會跳回上一層函數繼續執行）。

注意此時的執行環境（exection context）已經變了，所有setQueen函數內定義的變數全部回溯到上一層函數遞歸到下一層函數前的狀態，即執行setQueen( iQueen + 1 );這行代碼前的狀態，例如遞歸前i=2，iQueen=1，無論下一層函數里的i和iQueen怎樣變化，回溯後還是i=2，iQueen=1，然後緊接著執行未執行完的代碼。

D. 數據結構用棧和回溯法解決八皇後問題

#include <stdio.h>
#include <stdlib.h>

int Judge(int *p, int j)
//判斷當前棋子位置是否符合規則，是則返回1，否則返回0；
{
int i;
for(i=0;i<j;i++)
{
if(p[j]==p[i]) return 0;
if(abs(p[j]-p[i])==j-i) return 0;
}
return 1;
}

int main()
{
int a[8]; //a[i]表示第i行的後所在位置（a[3]=0表示第3行的皇後在第0列）
int i=0,j=0,k=0;

for(a[0]=0;a[0]<8;j=0,a[j]++)
for(a[++j]=0;a[j]<8;j=1,a[j]++)
if(Judge(a,j))
for(a[++j]=0;a[j]<8;j=2,a[j]++)
if(Judge(a,j))
for(a[++j]=0;a[j]<8;j=3,a[j]++)
if(Judge(a,j))
for(a[++j]=0;a[j]<8;j=4,a[j]++)
if(Judge(a,j))
for(a[++j]=0;a[j]<8;j=5,a[j]++)
if(Judge(a,j))
for(a[++j]=0;a[j]<8;j=6,a[j]++)
if(Judge(a,j))
for(a[++j]=0;a[j]<8;a[j]++)
if(Judge(a,j))
{
for(i=0;i<8;i++) printf("%d",a[i]);
printf("%3s"," ");
if(!(++k%7)) printf("\n");
}
printf("\n\n一共有%d種解法\n\n",k);
return 0;
}

E. 求教C語言回溯法寫出八皇後問題的92種解

(1)全排列

將自然數1~n進行排列，共形成n!中排列方式，叫做全排列。

例如3的全排列是：1/2/3、1/3/2、2/1/3、2/3/1、3/1/2、3/2/1，共3!=6種。

(2)8皇後（或者n皇後）

保證8個皇後不能互相攻擊，即保證每一橫行、每一豎行、每一斜行最多一個皇後。

我們撇開第三個條件，如果每一橫行、每一豎行都只有一個皇後。

將8*8棋盤標上坐標。我們討論其中的一種解法：

- - - - - - - Q

- - - Q - - - -

Q - - - - - - -

- - Q - - - - -

- - - - - Q - -

- Q - - - - - -

- - - - - - Q -

- - - - Q - - -

如果用坐標表示就是：(1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)

將橫坐標按次序排列，縱坐標就是8/4/1/3/6/2/7/5。這就是1~8的一個全排列。

我們將1~8的全排列存入輸入a[]中(a[0]~a[7])，然後8個皇後的坐標就是(i+1,a[i])，其中i為0~7。

這樣就能保證任意兩個不會同一行、同一列了。

置於斜行，你知道的，兩個點之間連線的斜率絕對值為1或者-1即為同一斜行，充要條件是|x1-x2|=|y1-y2|（兩個點的坐標為（x1,y1）(x2,y2)）。我們在輸出的時候進行判斷，任意兩個點如果滿足上述等式，則判為失敗，不輸出。

下面附上代碼：添加必要的注釋，其中全排列的實現看看注釋應該可以看懂：

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
intprinted;
//該函數用於畫圖，這里為了節約空間則略去
//讀者只需要將draw(a,k);去掉注釋即可畫圖
voiddraw(int*a,intk)
{
	inti,j;
	for(i=0;i<k;i++)
	{
		printf("	");
		for(j=0;j<k;j++)
			//有皇後輸出Q，否則輸出-
			if(a[i]-1==j)printf("Q");elseprintf("-");
		printf("
");
	}
	printf("
");

}
//遞歸實現全排列,a是數組，iStep是位置的測試點，k是皇後的個數，一般等於8
voidSettle(int*a,intiStep,intk)
{	
	inti,j,l,flag=1;
	//如果iStep的數字等於a之前的數字，則存在重復，返回
	for(i=0;i<iStep-1;i++)
		if(a[iStep-1]==a[i])return;
	//如果iStep==k，即遞歸結束到最後一位，可以驗證是否斜行滿足
	if(iStep==k)
	{
		//雙重循環判斷是否斜行滿足
		for(j=0;j<k;j++)
			for(l=0;l<k&&l!=j;l++)
				//如果不滿足，則flag=0
				if(fabs(j-l)==fabs(a[j]-a[l]))flag=0;
		//如果flag==1，則通過了斜行的所有測試，輸出。
		if(flag)
		{
			for(i=0;i<k;i++)
				printf("(%d,%d)",i+1,a[i]);
			printf("
");
			//如果去掉這里的注釋可以獲得畫圖，由於空間不夠，這里略去
		//	draw(a,k);
			//printed變數計算有多少滿足題意的結果，是全局變數
			printed++;
		}
		flag=1;
	}
	//如果未測試至最後末尾，則測試下一位（遞歸）
	for(i=1;i<=k;i++)
	{
		a[iStep]=i;
		Settle(a,iStep+1,k);
	}
}
voidmain()
{
	int*a;
	intk;
	//輸入維數，建立數組
	printf("Enterthesizeofthesquare:");
	scanf("%d",&k);
	a=(int*)calloc(k,sizeof(int));
	//清屏，從iStep=0處進入遞歸
	system("cls");
	Settle(a,0,k);
	//判斷最後是否有結果
	if(!printed)printf("Noanswersaccepted!
");
	elseprintf("%dstatesavailable!
",printed);
}
附輸出結果（輸入k=8）：
(1,1)(2,5)(3,8)(4,6)(5,3)(6,7)(7,2)(8,4)
(1,1)(2,6)(3,8)(4,3)(5,7)(6,4)(7,2)(8,5)
(1,1)(2,7)(3,4)(4,6)(5,8)(6,2)(7,5)(8,3)
(1,1)(2,7)(3,5)(4,8)(5,2)(6,4)(7,6)(8,3)
(1,2)(2,4)(3,6)(4,8)(5,3)(6,1)(7,7)(8,5)
(1,2)(2,5)(3,7)(4,1)(5,3)(6,8)(7,6)(8,4)
(1,2)(2,5)(3,7)(4,4)(5,1)(6,8)(7,6)(8,3)
(1,2)(2,6)(3,1)(4,7)(5,4)(6,8)(7,3)(8,5)
(1,2)(2,6)(3,8)(4,3)(5,1)(6,4)(7,7)(8,5)
(1,2)(2,7)(3,3)(4,6)(5,8)(6,5)(7,1)(8,4)
(1,2)(2,7)(3,5)(4,8)(5,1)(6,4)(7,6)(8,3)
(1,2)(2,8)(3,6)(4,1)(5,3)(6,5)(7,7)(8,4)
(1,3)(2,1)(3,7)(4,5)(5,8)(6,2)(7,4)(8,6)
(1,3)(2,5)(3,2)(4,8)(5,1)(6,7)(7,4)(8,6)
(1,3)(2,5)(3,2)(4,8)(5,6)(6,4)(7,7)(8,1)
(1,3)(2,5)(3,7)(4,1)(5,4)(6,2)(7,8)(8,6)
(1,3)(2,5)(3,8)(4,4)(5,1)(6,7)(7,2)(8,6)
(1,3)(2,6)(3,2)(4,5)(5,8)(6,1)(7,7)(8,4)
(1,3)(2,6)(3,2)(4,7)(5,1)(6,4)(7,8)(8,5)
(1,3)(2,6)(3,2)(4,7)(5,5)(6,1)(7,8)(8,4)
(1,3)(2,6)(3,4)(4,1)(5,8)(6,5)(7,7)(8,2)
(1,3)(2,6)(3,4)(4,2)(5,8)(6,5)(7,7)(8,1)
(1,3)(2,6)(3,8)(4,1)(5,4)(6,7)(7,5)(8,2)
(1,3)(2,6)(3,8)(4,1)(5,5)(6,7)(7,2)(8,4)
(1,3)(2,6)(3,8)(4,2)(5,4)(6,1)(7,7)(8,5)
(1,3)(2,7)(3,2)(4,8)(5,5)(6,1)(7,4)(8,6)
(1,3)(2,7)(3,2)(4,8)(5,6)(6,4)(7,1)(8,5)
(1,3)(2,8)(3,4)(4,7)(5,1)(6,6)(7,2)(8,5)
(1,4)(2,1)(3,5)(4,8)(5,2)(6,7)(7,3)(8,6)
(1,4)(2,1)(3,5)(4,8)(5,6)(6,3)(7,7)(8,2)
(1,4)(2,2)(3,5)(4,8)(5,6)(6,1)(7,3)(8,7)
(1,4)(2,2)(3,7)(4,3)(5,6)(6,8)(7,1)(8,5)
(1,4)(2,2)(3,7)(4,3)(5,6)(6,8)(7,5)(8,1)
(1,4)(2,2)(3,7)(4,5)(5,1)(6,8)(7,6)(8,3)
(1,4)(2,2)(3,8)(4,5)(5,7)(6,1)(7,3)(8,6)
(1,4)(2,2)(3,8)(4,6)(5,1)(6,3)(7,5)(8,7)
(1,4)(2,6)(3,1)(4,5)(5,2)(6,8)(7,3)(8,7)
(1,4)(2,6)(3,8)(4,2)(5,7)(6,1)(7,3)(8,5)
(1,4)(2,6)(3,8)(4,3)(5,1)(6,7)(7,5)(8,2)
(1,4)(2,7)(3,1)(4,8)(5,5)(6,2)(7,6)(8,3)
(1,4)(2,7)(3,3)(4,8)(5,2)(6,5)(7,1)(8,6)
(1,4)(2,7)(3,5)(4,2)(5,6)(6,1)(7,3)(8,8)
(1,4)(2,7)(3,5)(4,3)(5,1)(6,6)(7,8)(8,2)
(1,4)(2,8)(3,1)(4,3)(5,6)(6,2)(7,7)(8,5)
(1,4)(2,8)(3,1)(4,5)(5,7)(6,2)(7,6)(8,3)
(1,4)(2,8)(3,5)(4,3)(5,1)(6,7)(7,2)(8,6)
(1,5)(2,1)(3,4)(4,6)(5,8)(6,2)(7,7)(8,3)
(1,5)(2,1)(3,8)(4,4)(5,2)(6,7)(7,3)(8,6)
(1,5)(2,1)(3,8)(4,6)(5,3)(6,7)(7,2)(8,4)
(1,5)(2,2)(3,4)(4,6)(5,8)(6,3)(7,1)(8,7)
(1,5)(2,2)(3,4)(4,7)(5,3)(6,8)(7,6)(8,1)
(1,5)(2,2)(3,6)(4,1)(5,7)(6,4)(7,8)(8,3)
(1,5)(2,2)(3,8)(4,1)(5,4)(6,7)(7,3)(8,6)
(1,5)(2,3)(3,1)(4,6)(5,8)(6,2)(7,4)(8,7)
(1,5)(2,3)(3,1)(4,7)(5,2)(6,8)(7,6)(8,4)
(1,5)(2,3)(3,8)(4,4)(5,7)(6,1)(7,6)(8,2)
(1,5)(2,7)(3,1)(4,3)(5,8)(6,6)(7,4)(8,2)
(1,5)(2,7)(3,1)(4,4)(5,2)(6,8)(7,6)(8,3)
(1,5)(2,7)(3,2)(4,4)(5,8)(6,1)(7,3)(8,6)
(1,5)(2,7)(3,2)(4,6)(5,3)(6,1)(7,4)(8,8)
(1,5)(2,7)(3,2)(4,6)(5,3)(6,1)(7,8)(8,4)
(1,5)(2,7)(3,4)(4,1)(5,3)(6,8)(7,6)(8,2)
(1,5)(2,8)(3,4)(4,1)(5,3)(6,6)(7,2)(8,7)
(1,5)(2,8)(3,4)(4,1)(5,7)(6,2)(7,6)(8,3)
(1,6)(2,1)(3,5)(4,2)(5,8)(6,3)(7,7)(8,4)
(1,6)(2,2)(3,7)(4,1)(5,3)(6,5)(7,8)(8,4)
(1,6)(2,2)(3,7)(4,1)(5,4)(6,8)(7,5)(8,3)
(1,6)(2,3)(3,1)(4,7)(5,5)(6,8)(7,2)(8,4)
(1,6)(2,3)(3,1)(4,8)(5,4)(6,2)(7,7)(8,5)
(1,6)(2,3)(3,1)(4,8)(5,5)(6,2)(7,4)(8,7)
(1,6)(2,3)(3,5)(4,7)(5,1)(6,4)(7,2)(8,8)
(1,6)(2,3)(3,5)(4,8)(5,1)(6,4)(7,2)(8,7)
(1,6)(2,3)(3,7)(4,2)(5,4)(6,8)(7,1)(8,5)
(1,6)(2,3)(3,7)(4,2)(5,8)(6,5)(7,1)(8,4)
(1,6)(2,3)(3,7)(4,4)(5,1)(6,8)(7,2)(8,5)
(1,6)(2,4)(3,1)(4,5)(5,8)(6,2)(7,7)(8,3)
(1,6)(2,4)(3,2)(4,8)(5,5)(6,7)(7,1)(8,3)
(1,6)(2,4)(3,7)(4,1)(5,3)(6,5)(7,2)(8,8)
(1,6)(2,4)(3,7)(4,1)(5,8)(6,2)(7,5)(8,3)
(1,6)(2,8)(3,2)(4,4)(5,1)(6,7)(7,5)(8,3)
(1,7)(2,1)(3,3)(4,8)(5,6)(6,4)(7,2)(8,5)
(1,7)(2,2)(3,4)(4,1)(5,8)(6,5)(7,3)(8,6)
(1,7)(2,2)(3,6)(4,3)(5,1)(6,4)(7,8)(8,5)
(1,7)(2,3)(3,1)(4,6)(5,8)(6,5)(7,2)(8,4)
(1,7)(2,3)(3,8)(4,2)(5,5)(6,1)(7,6)(8,4)
(1,7)(2,4)(3,2)(4,5)(5,8)(6,1)(7,3)(8,6)
(1,7)(2,4)(3,2)(4,8)(5,6)(6,1)(7,3)(8,5)
(1,7)(2,5)(3,3)(4,1)(5,6)(6,8)(7,2)(8,4)
(1,8)(2,2)(3,4)(4,1)(5,7)(6,5)(7,3)(8,6)
(1,8)(2,2)(3,5)(4,3)(5,1)(6,7)(7,4)(8,6)
(1,8)(2,3)(3,1)(4,6)(5,2)(6,5)(7,7)(8,4)
(1,8)(2,4)(3,1)(4,3)(5,6)(6,2)(7,7)(8,5)
92statesavailable!

F. 回溯法解八皇後

用Turbo Pascal 5.0編譯即可。

Program Queen(input,output);
uses
crt;
const
T=true;
F=false;
W='?;
type
a8 = array[1..8 ] of integer;
a15 = array[1..15] of integer;
Var
x,y,n,count : integer;
Col,Q : a8;
Down,Up : a15;

(* Draw a n*n board *)
Procere Draw(x:integer;y:integer;n:integer);
var
i,j : integer;
Begin
clrscr;
gotoxy(28,1);
write('** ',n,'-Queen Problem **');
gotoxy(36,2);
write('1992.10 W.Y.Z');
{draw four corners}
gotoxy(x,y);write('?);
gotoxy(x+4*n,y);write('?);
gotoxy(x+4*n,y+2*n);write('?);
gotoxy(x,y+2*n);write('?);
{Draw the border }
for i:=2 to n do
begin
gotoxy(x,y+2*(i-1)); write('?);
gotoxy(x+4*(i-1),y); write('?);
gotoxy(x+4*(i-1),y+2*n); write('?);
gotoxy(x+4*n,y+2*(i-1)); write('?);
end;
for i:=1 to n do
begin
gotoxy(x,y+2*i-1); write('?);
gotoxy(x+4*n,y+2*i-1); write('?);
gotoxy(x+4*i-3,y); write('屯?);
gotoxy(x+4*i-3,y+2*n); write('屯?);
end;
{ Draw interpoint use '? }
for i:=2 to n do
for j:=2 to n do
begin
gotoxy(x+4*(j-1),y+2*(i-1));
write('?);
end;
{ Draw horizonal line use '哪? }
for i:=2 to n do
for j:=1 to n do
begin
gotoxy(x+4*j-3,y+2*(i-1));
write('哪?);
end;
{ Draw vertical line use '? }
for i:=1 to n do
for j:=2 to n do
begin
gotoxy(x+4*(j-1),y+2*i-1);
write('?);
end;
for i:=1 to n do
begin gotoxy(x+4*n+3,y+2*i-1);write(W); end;
end;

(* Input x,y,n then Draw the board *)
Procere Board;
var
LimitX,LimitY : integer;
Begin
clrscr;
repeat {Input n}
gotoxy(5,5);
write('Enter the number of queens N(0< N ?): ');
clreol;read(n);
until (0<n) and (n<=8);
LimitX:=80-(4*n+1);LimitY:=25-(2*n-1)-5;
repeat {Input x}
gotoxy(5,10);
write('Enter X of board-up-left (0 < X ?',LimitX,'){',LimitX div 2-2,'}: ');
clreol;read(x);
until (0<x) and (x<=LimitX);
repeat {Input y}
gotoxy(5,11);
write('Enter Y of board-up-left (4騤?',LimitY,'){',(LimitY +4) div 2,'}: ');
clreol;read(y);
until (4<=y) and (y<=LimitY);
Draw(x,y,n);
gotoxy(5,24);write('Press any key to begin...');
repeat until ReadKey<>'';
gotoxy(5,24);ClrEol;
end;

(* Initiate 4 arraies: Up,Down,Col,Q *)
Procere Initiate;
var
i:integer;
Begin
for i:=1 to 2*n-1 do
begin Up[i]:=0; Down[i]:=0; end;
for i:=1 to n do
begin Col[i]:=0; Q[i]:=0; end;
count:=1;
end;

(* The function to test (tr,tc) *)
Function Test(tr,tc:integer):Boolean;
Begin
if Up[tr+tc-1]=1 then Test:=F
else if Down[tr-tc+8]=1 then Test:=F
else if Col[tc]=1 then Test:=F
else Test:=T;
end;

(* An sound procere when put a queen on (r,c) *)
Procere Laugh;
Begin
sound(150);
delay(50000);
Nosound;
delay(45000);
end;

(* Put Queen on (pr,pc) *)
Procere PutOn(pr,pc:integer);
Begin
Q[pr]:=pc; Col[pc]:=1;
Up[pr+pc-1]:=1; Down[pr-pc+8]:=1;
gotoxy(x+4*pc-2,y+2*pr-1);
write(W);
gotoxy(x+4*n+3,y+2*pr-1);write(' ');
Laugh;
end;

(* An sound procere when move a queen from (r,c) *)
Procere Cry;
Begin
sound(220);
delay(50000);
Nosound;
delay(45000);
end;

(* Move Queen from (cr,cc) *)
Procere ClrOn(cr,cc:integer);
Begin
Q[cr]:=0 ; Col[cc]:=0;
Up[cr+cc-1]:=0; Down[cr-cc+8]:=0;
gotoxy(x+4*cc-2,y+2*cr-1);
write(' ');
gotoxy(x+4*n+3,y+2*cr-1);write(W);
Cry;
end;

(* a sound procere when find a solution *)
Procere Sing;
var
i,freq:integer;
Begin
Randomize;
for i:=1 to 10 do
begin
freq:=Random(2900)+100;
Sound(freq);Delay(5000);
NoSound;
end;
end;

(* Print one solution *)
Procere PrintQ;
var
i:integer;
ch:char;
Begin
gotoxy(5,22);
write('I find the solution of NO.',count,':');
inc(count);
gotoxy(5,23);
for i:=1 to n do write(Q[i]:3);
Sing;
gotoxy(5,24);
write('Press any key to other solutions(Q to break)...');
repeat
ch:=upcase(ReadKey);
if ch='Q' then Halt(0);
until ch<>'';
gotoxy(5,24);ClrEol;
end;

(* N Queens Problem *)
Procere N_Queen(r:integer);
var
c:integer;
Begin
for c:=1 to n do
begin
if test(r,c) then
begin
PutOn(r,c);
if r=n then PrintQ
else N_Queen(r+1);
ClrOn(r,c);
end;
end;
end;

(* Print end-information of this program *)
Procere Final;
Begin
window(5,22,80,24); clrscr;
writeln('I find all of the ',count-1,' solutions !');
writeln;
write('Press any key to end.');
repeat until ReadKey<>'';
window(1,1,80,25);
end;

(* The Queen problem *)
Begin
Board;
Initiate;
N_Queen(1);
Final;
End.

G. 8皇後問題回溯演算法程序修改（C＋＋）

int main(){
int q[8],c,i,j,count=0;
q[0]=0;
c=0;

while (c!=-1)
{
c++;

if (c==8)
{
cout<<"chess No."<<++count<<endl;
cout<<" 0 1 2 3 4 5 6 7"<<endl;
for (i=0;i<8;i++){
cout<<i;
for (j=0;j<8;j++)
if (q[j]==i)
cout<<" Q";
else
cout<<" .";
cout<<endl;
}

c--;
}
else
{
q[c]=-1;
}

while (c!=-1)
{
q[c]++;
if (q[c]==8)
{
c--;
}
else
{
for (i=0;i<c;i++)
if (q[c]==q[i]||abs(q[c]-q[i])==c-i)
break;
if (i==c)
{
break;
}
}
}
}
}

H. 請編寫8皇後問題（即在8*8的棋盤了放置8個皇後，互相之間不能攻擊到）的回溯演算法

public static void Main(string[] args)
{
solveQueens(8);
}

public static void solveQueens(int n)
{
int[] queens = new int[n];
for (int i = 0; i < n; ++i)
{
queens[i] = 0;
}
solve(queens, 0);
}

private static void solve(int[] queens, int depth)
{
int length = queens.Length;
if (depth == length) {
printQueens(queens, length);
} else {
for (int i = 0; i < length; ++i) {
if (isValid(queens, depth, i)) {
queens[depth] = i;
solve(queens, depth + 1);
}
}
}
}

private static bool isValid(int[] queens, int depth, int col)
{
for (int i = 0, value; i < depth; ++i)
{
value = queens[i];
if (value == col || System.Math.Abs(value - col) == (depth - i)) {
return false;
}
}
return true;
}

private static void printQueens(int[] queens, int n)
{
for (int i = 0, value; i < n; ++i)
{
value = queens[i];
for (int j = 0; j < value; ++j)
{
Console.Write(".");
}
Console.Write("Q");
for (int j = value + 1; j < n; ++j)
{
Console.Write(".");
}
Console.WriteLine();
}
Console.WriteLine();
}

I. 八皇後問題求解方法分類

八皇後問題
{
「八皇後」問題
遞歸法
求解
(
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

J. 八皇後演算法 free pascal

〖問題描述〗
在一個8×8的棋盤里放置8個皇後，要求每個皇後兩兩之間不相"沖"（在每一橫列豎列斜列只有一個皇後）。

〖問題分析〗(聿懷中學呂思博)
這道題可以用遞歸循環來做，分別一一測試每一種擺法，直到得出正確的答案。主要解決以下幾個問題：
1、沖突。包括行、列、兩條對角線：
（1）列：規定每一列放一個皇後，不會造成列上的沖突；
（2）行：當第I行被某個皇後佔領後，則同一行上的所有空格都不能再放皇後，要把以I為下標的標記置為被佔領狀態；
（3）對角線：對角線有兩個方向。在同一對角線上的所有點（設下標為(i,j)），要麼(i+j)是常數，要麼(i-j)是常數。因此，當第I個皇後佔領了第J列後，要同時把以(i+j)、(i-j)為下標的標記置為被佔領狀態。
2、數據結構。
（1）解數組A。A[I]表示第I個皇後放置的列；范圍：1..8
（2）行沖突標記數組B。B[I]=0表示第I行空閑；B[I]=1表示第I行被佔領；范圍：1..8
（3）對角線沖突標記數組C、D。
C[I-J]=0表示第（I-J）條對角線空閑；C[I-J]=1表示第（I-J）條對角線被佔領；范圍：-7..7
D[I+J]=0表示第（I+J）條對角線空閑；D[I+J]=1表示第（I+J）條對角線被佔領；范圍：2..16

〖演算法流程〗
1、數據初始化。
2、從n列開始擺放第n個皇後（因為這樣便可以符合每一豎列一個皇後的要求），先測試當前位置(n,m)是否等於0（未被佔領）:
如果是，擺放第n個皇後，並宣布佔領(記得要橫列豎列斜列一起來哦)，接著進行遞歸；
如果不是，測試下一個位置(n,m+1)，但是如果當n<=8,m=8時，卻發現此時已經無法擺放時，便要進行回溯。
3、當n>;8時，便一一列印出結果。

〖優點〗逐一測試標准答案，不會有漏網之魚。

〖參考程序〗queen.pas
----------------------------------------------------------------------------
programtt;
vara:array[1..8]ofinteger;
b,c,d:array[-7..16]ofinteger;
t,i,j,k:integer;
procereprint;
begin
t:=t+1;
write(t,'');
fork:=1to8dowrite(a[k],'');
writeln;
end;

proceretry(i:integer);
varj:integer;
begin
forj:=1to8do
if(b[j]=0)and(c[i+j]=0)and(d[i-j]=0)then
begin
a:=j;
b[j]:=1;
c[i+j]:=1;
d[i-j]:=1;
ifi<8thentry(i+1)
elseprint;
b[j]:=0;
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
fork:=-7to16do
begin
b[k]:=0;
c[k]:=0;
d[k]:=0;
end;
try(1);
end.

==========================================
這是N皇後問題，看看吧：
在N*N的棋盤上，放置N個皇後，要求每一橫行每一列，每一對角線上均只能放置一個皇後，問可能的方案及方案數。
const max=8;
var i,j:integer;
a:array[1..max] of 0..max; //放皇後數組
b:array[2..2*max] of boolean; // 『/』對角線標志數組}
c:array[-(max-1)..max-1] of boolean;// 『\』對角線標志數組}
col:array[1..max] of boolean; //列標志數組}
total:integer; //統計總數}

procere output; //這里是輸出過程
var i:integer;
begin
write('No.':4,'[',total+1:2,']');
for i:=1 to max do write(a[i]:3);write(' ');
if (total+1) mod 2 =0 then writeln; inc(total);
end;

function ok(i,dep:integer):boolean; //判斷第dep行第i列可放否？
begin
ok:=false;
if ( b[i+dep]=true) and ( c[dep-i]=true) and
(col[i]=true) then ok:=true
end;

procere try(dep:integer);
var i,j:integer;
begin
for i:=1 to max do //每一行均有max種放法，對吧？xixi~~~~
if ok(i,dep) then begin
a[dep]:=i;
b[i+dep]:=false; // 『/』對角線已放標志
c[dep-i]:=false; // 『\』對角線已放標志
col[i]:=false; // 列已放標志
if dep=max then output
else try(dep+1); // 遞歸下一層
a[dep]:=0; //取走皇後,回溯
b[i+dep]:=true; //恢復標志數組
c[dep-i]:=true;
col[i]:=true;
end;
end;

begin
for i:=1 to max do begin a[i]:=0;col[i]:=true;end;
for i:=2 to 2*max do b[i]:=true;
for i:=-(max-1) to max-1 do c[i]:=true;
total:=0;
try(1);
writeln('total:',total);
end.