回溯算法八皇后

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.