queen.cpp

此程序源码为回溯算法中的n后问题

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

#include "stdafx.h"
#include "Queen.h"

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

Queen::Queen()
{

}

Queen::~Queen()
{

}

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) {
	//////////////////////////////////////////////////////////////////////////
	// 输出当前解
		
/*	for (int i=1;i<=n;i++) {
		printf("%d\t",x[i]);
		if(i%10 ==0 && n>0)
		  printf("\n");
	} 
	printf("\n");
*/		sum++;//对解的个数加1;
	}
   else
	   for (int i =1;i<=n;i++) {//对于t位置的数值，取遍所有可能的解
		   x[t] = i;
		   if (Place(t)) {
			   Backtrack(t+1);
		   }
	   }
}
int nQueen(int n)
{
	Queen 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;
}