sy7.cpp

用回溯法实现n皇后问题

#include <iostream>
using namespace std;

//***********检查位置是否合法的函数Place(int k,int *x)*****************
bool Place(int k,int *x)
{
	for(int i=1;i<k;i++)
		if((x[k]==x[i])||(abs(k-i)==abs(x[k]-x[i])))//判断是否同列、同斜率
			return false;
	return true;
}

//************摆放皇后的函数Queue(int n)********************************
void Queue(int n)
{   
	int *x=new int[n];//x[i]存放第i个皇后摆放的列号:1<=x[i]<=n
	int i,k=1,j;
	for(i=1;i<=n;i++)//初始化
		x[i]=0;
	while(k>=1)//开始摆放
	{
		x[k]=x[k]+1;
		while((x[k]<=n)&&!Place(k,x))//寻找合法的摆放位置（列号）
			x[k]++;//x[k]=x[k]+1;
		if((x[k]<=n)&&(k==n))//判断是否已得出一解，若是则打印此解
		{
			for(i=1;i<=n;i++)
			{
				for(j=1;j<=x[i];j++)
					cout<<"-";
			    cout<<x[i];
				for(j=x[i];j<=n;j++)
					cout<<"-";
				cout<<endl;
			}
			cout<<endl<<endl;
		}
		else if((x[k]<=n)&&(k<n))//若是没得出解，判断是否将所用皇后摆放完毕，若没有则继续
			k=k+1;
		else//若是到此，说明没求出解之前就走不下去（即没有合适列号），回溯
		{
			x[k]=0;
			k=k-1;
		}
	}
}

void main()
{
	int n;
	cout<<"请输入皇后数量n:";
    cin>>n;
	Queue(n);
}