8queen.c

随机生成八皇后棋盘

/*
	八皇后问题
	算法：爬山法
*/
#include   <stdlib.h>   
#include   <stdio.h>   
#include   <time.h>
#include   <math.h> 
#define	 MAX	8

int p[MAX][MAX];
int s[MAX][MAX];
int c;

void   random(int p[MAX][MAX])//随机数生成器   
{   
	int   n;   
    time_t   t;   
    printf("棋盘初始化\n");  
  	srand((unsigned)   time(&t));//以当前时间初始化   
	for(n=0;   n<MAX;   n++)
	{	
		int m;
		m=rand()%8;
		p[m][n]=s[m][n]=1;
		//printf("(%d,%d)\n",m,n);
	}
	return;   
}   

int CountCollision(int a[MAX][MAX])//计算皇后冲突对数
{	
	int m,n;
	int conflit=0;
	int y=0;
	int i;

	for(m=0;m<MAX;m++)//横向扫描
	{
		y=0;
		for(n=0;n<MAX;n++)
		{
			if(a[m][n]==1)
				y++;
		}
		conflit+=(y*(y-1)/2);
	}

	for(i=0;i<MAX;i++)//斜向扫描
	{
		y=0;
		m=i;n=0;
		while(m>-1&&m<MAX&&n>-1&&n<MAX)
		{
			if(a[m][n]==1)
				y++;
			m++;
			n++;
		}
		conflit+=(y*(y-1)/2);
	}

	for(i=1;i<MAX;i++)
	{	
		y=0;
		m=0;n=i;
		while(m>-1&&m<MAX&&n>-1&&n<MAX)
		{
			if(a[m][n]==1)
				y++;
			m++;
			n++;
		}
		conflit+=(y*(y-1)/2);
	}

	for(i=MAX-1;i<MAX;i--)
	{
		if(i<0)break;
		y=0;
		m=i;n=0;
		while(m>-1&&m<MAX&&n>-1&&n<MAX)
		{
			if(a[m][n]==1)
				y++;
			m--;
			n++;
		}
		conflit+=(y*(y-1)/2);
	}

	for(i=1;i<MAX;i++)
	{
		y=0;
		m=MAX-1;n=i;
		while(m>-1&&m<MAX&&n>-1&&n<MAX)
		{
			if(a[m][n]==1)
				y++;
			m--;
			n++;
		}
		conflit+=(y*(y-1)/2);
	}
	
	return conflit;
}

void PrintTable(int p[MAX][MAX])
{
	int m,n;
	for(m=0;m<MAX;m++)
	{
		printf("{");
		for(n=0;n<MAX;n++)
		{
			printf("%d,",p[m][n]);
		}
		printf("}\n");
	}	

}

int RandomRow()//随机生成行号   
{   
    time_t   t;   
  	srand((unsigned)   time(&t));//以当前时间初始化   
	return (rand()%8);   
}   


int main()
{	
	int x;
	int i,k;
	random(p);//初始化棋盘
	PrintTable(p);//打印棋盘初始状态
	c=CountCollision(p);
	printf("初始皇后冲突对数：%d\n",c);//打印初始皇后冲突对数
	

	for(i=0;i<MAX;i++)
	{	int j;
		while(1)
		{
			k=RandomRow();//随机选取该列中的一格，若到该位置后，冲突对数将减少，则移动到该位置
			if(s[k][i]!=1)
			{
				for(j=0;j<MAX;j++)
					s[j][i]=0;
				s[k][i]=1;
			}
			x=CountCollision(s);
			if(x<c)
			{
				c=x;
				for(j=0;j<MAX;j++)
					p[j][i]=0;
				p[k][i]=1;
				printf("第%d列皇后：移动->第%d行\n",i,k);

				break;
			}
			else
			{
				for(j=0;j<MAX;j++)
					s[j][i]=p[j][i];
			}


		}
	}
	
	PrintTable(p);//打印棋盘最终状态
	
}