queen.cpp

回溯算法解决n皇后问题

// Queen.cpp: implementation of the Queen class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Queen.h"
#include "math.h"
#include "iostream.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

//##ModelId=46189A5F019B
Queen::Queen()
{
}

//##ModelId=46189A5F019C
Queen::~Queen()
{
}

//##ModelId=46189A5F019E
void Queen::NQueens(int n)
{
	int k;
	N=n;
	X=new int[n+1];
	X[1]=0;
	k=1;
	while(k>0)
	{
		X[k]=X[k]+1;
		while(X[k]<=n&&!Place(k))
		{
			X[k]=X[k]+1;
		}
		if(X[k]<=n)
		{
			if(k==n)
				Print(X);
			else 
			{
				k=k+1;
				X[k]=0;
			}
		}
		else k=k-1;
	}
}

//##ModelId=46189A5F01A6
bool Queen::Place(int k)
{
	int i;
	i=1;
	while(i<k)
	{
		if(X[i]==X[k]||abs(X[k]-X[i])==abs(k-i))
			return false;
		else 
			i=i+1;
	}
	return true;
}

void Queen::Print(int X[])
{
	int i;
	for(i=1;i<=N;i++)
		cout<<X[i]<<"\t";
	cout<<endl;
}