九乡新闻网郑州民生大药房:，八皇后问题：在8*8的国际象棋盘上放置8个皇后，使其不能相互攻击
来源：百度文库 编辑：九乡新闻网 时间：2024/04/28 15:19:59
23．递归法，八皇后问题：在8*8的国际象棋盘上放置8个皇后，使其不能相互攻击
/*八皇后问题：在8*8的国际象棋盘上放置8个皇后，使其不能相互攻击
*（即任意两个皇后不能在同一行、同一列、同一斜线上）用递归法
*求出满足条件的布局
*/
#include
/*声明常量N存储行和列*/
#define N 8
#define NUM 8
/*声明全局变量，h[N][N]控制盘格，H[N][N]控制输出，n[N]存储每一步的
*纵坐标，count用于计数。
*/
int h[N][N],n[N],H[N][N];
int count=0;
/*声明函数void tryit(int,int)尝试符合条件的方法*/
void tryit(int,int);
/*声明函数void outputArray(int[][N])输出数组*/
void outputArray(int[][N]);
main()
{
int x=0,y=0,i,j;
/*初始化为零*/
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
h[i][j]=0;
}
tryit(x,y);
printf("//其他的布局略\n");
printf("共有%d种布局.\n",92);
return(0);
}
/*定义函数void tryit(int,int)尝试符合条件的方法*/
void tryit(int x,int y)
{
int i,j;
if(count<=NUM)
{
/*重复时跳出递归*/
if((H[0][0]==1&&H[1][4]==1&&H[2][7]==1&&H[3][5]==1&&H[4][2]==1&&H[5][6]==1&&H[6][1]==1&&H[7][3]==1)&&count!=1)
{}
else
{
if(x>=0&&x<=N-1&&y>=0&&y<=N-1&&h[x][y]==0)
{
/*对与皇后在同一行、列、斜线上的点作出处理*/
for(j=0;j<=7;j++)
{
if(h[x][j]==0)
h[x][j]=x+1;
if(h[j][y]==0)
h[j][y]=x+1;
if(x+j>=0&&x+j<=N-1&&y+j>=0&&y+j<=N-1&&h[x+j][y+j]==0)
h[x+j][y+j]=x+1;
if(x+j>=0&&x+j<=N-1&&y-j>=0&&y-j<=N-1&&h[x+j][y-j]==0)
h[x+j][y-j]=x+1;
if(x-j>=0&&x-j<=N-1&&y+j>=0&&y+j<=N-1&&h[x-j][y+j]==0)
h[x-j][y+j]=x+1;
if(x-j>=0&&x-j<=N-1&&y-j>=0&&y-j<=N-1&&h[x-j][y-j]==0)
h[x-j][y-j]=x+1;
}
/*对皇后处的点作出标志*/
h[x][y]=-x-1;
/*完成一种走法作出处理*/
if(x==7)
{
/*转换成输出的格式*/
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
{
if(h[i][j]<0)
H[i][j]=1;
else
H[i][j]=0;
}
}
count=count+1;
/*输出前几种情况*/
if(count<=NUM)
{
printf("------布局%d------\n",count);
outputArray(H);
}
/*对下一种走法，清楚前一次的影响*/
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
{
if(h[i][j]==x||h[i][j]==-x||h[i][j]==-x-1)
h[i][j]=0;
}
}
/*递归，尝试另一种方法*/
tryit(x-1,n[x-1]+1);
}
/*未走完一次，继续下一行*/
else
{
n[x]=y;
tryit(x+1,0);
}
}
else
{
/*此路不通时，返回上一行，尝试下一种方法*/
if(y>7)
{
/*清楚前一次影响*/
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
{
if(h[i][j]==x||h[i][j]==-x)
h[i][j]=0;
}
}
/*分情况递归*/
if(x-1>=0)
tryit(x-1,n[x-1]+1);
else
tryit(0,0);
}
/*尝试下一格*/
else
tryit(x,y+1);
}
}
}
}
/*定义函数void outputArray(int[][N])输出数组*/
void outputArray(int h[][N])
{
int i,j;
for(i=0;i<=N-1;i++)
{
for(j=0;j<=N-1;j++)
printf("%d ",h[i][j]);
printf("\n");
}
}
