8queens.cpp

编写程序对八皇后问题进行求解：在8行8列的棋盘上放置8个皇后

/*17． 编写程序对八皇后问题进行求解：在8行8列的棋盘上放置8个皇后，
使任一个皇后都不能吃掉其他的7个皇后（注：皇后可吃掉与她处于同行或同列或同一对角线上的其他棋子），
并将结果以某种方式显示出来。
	例如，当求出下述的一个解时，
	可输出如下信息来表示该解（输出了表示摆放皇后的坐标位置以及"棋盘状态"- 棋盘中有皇后的位置放一个"Q"字符，其他位置为"+"字符）。
(1,1) (5,2) (8,3) (6,4) (3,5) (7,6) (2,7) (4,8)
 Q + + + + + + +
 + + + + + + Q +
 + + + + Q + + +
 + + + + + + + Q
 + Q + + + + + +
 + + + Q + + + +
 + + + + + Q + +
 + + Q + + + + +
*/

#include<iostream>
#include<cmath>
using namespace std;
class queen
{
private:
	int *x;
	int n;
	int sum;
public:
	void initail(int j);
	bool place(int k);
	void Queen();
	void display();
};
void queen::initail(int j)
{
	n=j;
	sum=0;
	x=new int[n+1];
	for(int i=0;i<=n;i++)
		x[i]=0;
	Queen();
	delete []x;
	
}
bool queen::place(int k)
{
	for(int i=1;i<k;i++)
		if(abs(i-k)==abs(x[i]-x[k])||(x[i]==x[k]))
			return false;
		return true;
}
void queen::Queen()
{
	x[1]=0;
	int k=1;

	while(k>0)
	{
		x[k]=x[k]+1;
	
		while((x[k]<=n)&&(!place(k)))
			x[k]++;
		if(x[k]<=n)
			if(k==n)
			{
				display();
				cout<<endl;
				sum++;
			}
			else
			{
				k++;
			    x[k]=0;
			}
		else
			k--;
	
	}
	cout<<"一共有"<<sum<<"种摆法！"<<endl;
}
void queen::display()
{
	for(int i=1;i<=n;i++)
		cout<<'('<<i<<','<<x[i]<<')'<<" ";
	cout<<endl;
	for(i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)

	    	if(x[i]==j)
			  cout<<'Q'<<' ';
			else cout<<'+'<<' ';
   	cout<<endl;

	}

}
int main()
{
	queen Q;
	Q.initail(8);
	return 0;
}