kingho.cpp

皇后问题：在N*N的方格里放置皇后

#include "iostream.h"
struct stack
{
	int x;
	int y;
};
class point
{
public:
	stack * base;			
	stack * top;
	void push(stack temp);		//把temp进栈
	stack pop();				//出栈
	bool chack(stack temp);		//检查是不是temp是不是合适的
	bool full();				//检查是不是为满栈，若为满栈则执行下面的输出
	void view();				//显栈内内容
	int xtop();					//取栈顶元素的X
	int ytop();					//取栈顶元素的Y
	int n;						//栈的长度
};
void point::push(stack temp)
{
	if(top!=NULL)
	{
		top++;
		*top=temp;
		
	}
	else
	{
		cout<<"error !  top==NULL "<<endl;
	}
}
stack point::pop()
{
	stack temp;
	if(top!=base)
	{
		temp=*(top);
		top--;
		return temp;
	}
	else 
	{
		temp.x=-1;
		temp.y=-1;
		return   temp;
	}
}
bool point::chack(stack temp)
{
	stack * p;
	p=base;
	while (p<top)
	{
		if(((p+1)->y!=temp.y)&&((p+1)->x-temp.x!=(p+1)->y-temp.y)&&((p+1)->x-temp.x!=(temp.y-(p+1)->y)))
		{
			p++;
		}
		else
			break;
	}
	if(p>=top)
		return 1;
	else return 0;
}
bool point::full()
{
	if((top-base)>=(n))
	{
		return 1;
	}
	else return 0;
}
void point::view()
{
	stack *p;
	p=base;
	while(p<top)
	{

		cout<<"("<<(p+1)->x<<","<<(p+1)->y<<")"<<"  ";
		p++;
	}
	cout<<endl;
}
int point::xtop()
{
	if(base==top)
		return 0;
	else
		return (top)->x;
}
int point::ytop()
{
	if(base==top)
		return 0;
	else
		return (top)->y;
}
void main()
{
	cout<<"**********************皇后问题****************"<<endl;
	cout<<"--------------------------作者：陶发辉"<<endl;
	int k=0;			//记录有几个排法
	stack a;
	int * *tt;
	cout<<"how money kingho"<<endl;
	int n,x,y;
	x=y=0;
	cin>>n;
	point st;
	st.n=n;
	st.base=new stack[n+1];
	tt=new int*[n];
	for(int i=0;i<n;i++)
		tt[i]=new int[n];
	for(i=0;i<n;i++)
		for(int j=0;j<n;j++)
			tt[i][j]=0;
	st.top=st.base;
	a.x=a.y=0;
	while(a.x<n||a.y<=n)
	{
		if(a.y>=n)
				{
					a=st.pop();
					a.y++;
				}
		if(a.x>=0)
		{
			while(a.y<n)
			{
				if(st.base==st.top)
				{
					st.push(a);
					a.x++;
					a.y=0;
					break;
				}
				else
				{
					if((st.base!=st.top)&&st.chack(a))
					{
						bool mm;
						mm=st.full();
						st.push(a);
						a.x++;
						a.y=0;
						if(st.full())
						{
							k++;
							cout<<"第"<<k<<"个排法："<<endl;
							//st.view();原来想以这种方式输出，但不直观，改成了矩阵;
							stack *k;
							k=st.base+1;
							for(i=0;i<n;i++)
							{
								tt[k->x][k->y]=1;
								k++;
							}
							cout<<"----------------------------------------------------------"<<endl;
							for(i=0;i<n;i++)
							{
									for(int j=0;j<n;j++)
									cout<<tt[i][j]<<" ";
									cout<<endl;
								
							}
							cout<<"------------------------------------------------------------"<<endl;
							for(i=0;i<n;i++)
							{
								for(int j=0;j<n;j++)
									tt[i][j]=0;
							}

							//st.view();
							a=st.pop();
							a.y++;
					
						}
						break;
					}
					else
					{
					a.y++;
				
					}
				}

			}
		}
		else
			break;
	}

}