n后问题.cpp

回溯法实现多个经典算法

// n后问题

#include <iostream.h>
#include <math.h>

class Queen
{
	friend int nQueen(int);
private:
	bool Place(int k);
	void Backtrack(int t);
	int	n,	// 皇后个数
		*x;	// 当前解
	long sum;	// 已找到的可行方案数
};

bool Queen::Place(int k)
{
	for (int j=0; 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+1>n) sum++;
	else
		for (int i=0; i<n; i++)
		{
			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];
	for (int i=0; i<n; i++) p[i]=0;
	X.x=p;
	X.Backtrack(0);
	delete [] p;
	return X.sum;
}

void main()
{
	int n=0;
	while (n<1)
	{
		cout<<"n = ";
		cin>>n;
	}
	cout<<"\nSum = "<<nQueen(n);
	cout<<"\n\n";
}