八皇后.cpp

数据结构常用算法

#include<iostream.h>
#include<stdio.h>
int N=8; 
int weizhi[10][10]; 
int p=0; 
int buju(int x1,int y1) 
{
	int a1,b1; 
	for(a1=0;a1<x1;a1++)
	{ 
		for(b1=0;b1<N;b1++)
		{ 
			if(weizhi[a1][b1]==1)
			{    //有一个条件不符合则返回0
				if(a1==x1||b1==y1)   return 0; //在同一行或同一列,返回0
				if((a1-b1)==(x1-y1)) return 0; //同一对角线,返回0
				if((a1+b1)==(x1+y1)) return 0; //同一对角线,返回0
			} 
		} 
	} 
	return 1;      //满足三个条件则返回1
} 
int destroy(int w) 
{    
	int x,y; 
	for(x=0;x<N;x++) 
		if(weizhi[w][x]==1) //把每行的布局撤消
		{ 
			weizhi[w][x]=0; 
			y=x; 
		} 
		return y;
} 
int out() //输出
{
	int t,y;
	cout<<"八皇后布局为："<<endl;
	cout<<"****************"<<endl;  
	p++; 
	for(t=0;t<N;t++)
	{ 
		for(y=0;y<N;y++)
		{ 
			cout<<weizhi[t][y]<<' ';  
		} 
		cout<<endl;
	} 
	cout<<endl<<"****** "<<p<<" ********"<<endl;
	getchar();
	return 0; 
} 
void main() 
{ 
	int m,n,i,j; 
	for(m=0;m<N;m++) 
		for(n=0;n<N;n++) 
			weizhi[m][n]=0; 
	m=0;n=0;j=0; 
	do
	{
		for(n=0;n<N;n++) 
		{ 
			i=buju(m,n); 
			if(m==N-1 && i==1)
			{  //布局完成并且合法时,输出当前棋盘
				weizhi[m][n]=1; //布局完成,位置合适,置1
				cout<<"键入回车键继续"<<endl;
				out();  //输出
			
				i=0;
				weizhi[m][n]=0;
			} 
			if(i==1)      //布局没完成,但位置合适,则置1
			{ weizhi[m][n]=1; break;} 
			if(n==N-1&&i==0) 
			{//如果排到最后没有合适布局,撤消以前的布局,重新再来
				do
				{ 
					m--; 
					n=destroy(m); 
					if(m==0 && n==N-1 && j==1) break; 
				}while(n>=N-1); 
			} 
		} 
		j=1; 
		m++; 
		if(m>=N)
			m=0; 
	}while(m<N&&n<N); 
	cout<<endl<<"********IT'S OVER!!********"<<endl; 
}