queen.cpp

算法设计中的经典问题

// QUEEN.cpp: implementation of the CQUEEN class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "符号三角形，n皇后，圆排列.h"
#include "QUEEN.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

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

CQUEEN::CQUEEN()
{

}

CQUEEN::~CQUEEN()
{

}


bool CQUEEN::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 CQUEEN::Backtrack(int t)
{
	if(t>n)sum++;
	else
		for(int i=1;i<=n;i++)
		{
			x[t]=i;
		if(Place(t))
			Backtrack(t+1);
		}
//			for(int i=1;i<n;i++)
//	      cout<<x[i]<<endl;
}

int nQueen(int n)
{
	CQUEEN x;
	x.n=n;
	x.sum=0;
	int *p=new int [n+1];
	for(int i=0;i<=n;i++)
		p[i]=0;
	x.x=p;
	x.Backtrack(1);
	delete[]p;

	return x.sum;

}