八皇后.cpp

软件课程设计（1） 是一些非常经典的程序

#include <iostream>
using namespace std;
#include <stdlib.h>


class Queen
{
	friend int nQueen(int n);
private:
	bool Place(int k);         //判断是否可在k行i列放皇后，是返回true
	void BackTrack(int t);     //回溯函数
	void Display();            //打印出一种布局
	int n;                     //皇后个数
	int *x;                    //存放第k行皇后在第x[k]列
	long sum;                  //已找出的布局数
};




bool Queen::Place(int k)
{
	for(int j=1;j<k;j++)
		if((abs(k-j)==abs(x[j]-x[k]))||x[j]==x[k])//列，对角线，斜对角线中有相同值
			return false; 
	return true;
}


void Queen::BackTrack(int t)    
{
	if(t>n) {sum++;Display();}
	else for(int i=1;i<=n;i++)
	{
		x[t]=i;
		if(Place(t))BackTrack(t+1);
	}
}


void  Queen::Display()
{
	int *m;
	m=x;
	for(int e=1;e<=n;e++)
		cout<<"("<<e<<","<<m[e]<<")";
	    cout<<endl;
	for(e=1;e<=n;e++)
	{
		for(int f=1;f<=n;f++)
		{
			if(x[e]==f) cout<<"Q ";
			else cout<<"+ ";
		}
	cout<<endl;	
	}	
}


int nQueen(int n)
{
	Queen Q;
	Q.n=n;
	Q.sum=0;
	int *p=new int[n+1];
	for(int i=0;i<n;i++)
		p[i]=0;
	Q.x=p;
	Q.BackTrack(1);
	delete []p;
	return Q.sum;
}

int main()
{
	int n;
	int choose;
	do
	{cout<<"请输入皇后的个数：";
     cin>>n;
	 cout<<n<<"皇后问题共有"<<nQueen(n)<<"种解法。\n";
     cout<<"继续请按1，终止请按其他\n";
	 cin>>choose;
	}
	while(choose==1);
	return 0;
}