nqueen.cpp

N皇后问题求解

#include<iostream>
#include<cmath>

using namespace std;

bool place(int i, int k);
void nqueen(int i, int n);

int n=0;
int *x=NULL;

int main()
{
	cin>>n;
	x=new int[n];
	if(!x){
		cout<<"allocation failure!"<<endl;
		return 1;
	}
	//cout<<"test1"<<endl;
	for(int i=0;i<n;i++)
		x[i]=-1;

	//cout<<"test2"<<endl;
	
	nqueen(0,n);

	delete []x;
	return 0;
}

bool place(int i, int c)
{
	for(int num=0;num<i;num++)
	{
		if(x[num]==c || (abs(x[num]-c)==abs(num-i)))
			return false;
	}
	return true;
}

void nqueen(int i,int n)
{
	for(int k=0;k<n;k++)
	{
		if(place(i,k)){
			//cout<<"test3"<<endl;
			x[i]=k;
			if(i==(n-1)){
				for(int h=0;h<n;h++)
					cout<<x[h]<<" ";
				cout<<endl;
				//return;
			}
			else
				nqueen(i+1,n);
		}
	}
}