n皇后问题.cpp

算法分析中

#include<iostream>
using namespace std;
/*
解空空间是完全N叉树
x[i]表示第i个皇后放在第i行的第x[i]列
*/
class Queen
{
	friend int nQueen(int);
private:
	bool Place(int k);
	void Backtrack(int t);
	int n;
	//皇后个数
	int *x;
	//当前解
	long sum;
	//当前已经找到的可行方案数
};

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 )
	{
		sum++;
	}
	else
	{
		for( int i = 1; i <= n; ++i )
		//如果是全排列的则需要回溯时复原原来的值
		//完全N叉树确定值范围则不需要这样
		{
			x[t] = i;
			//将第t个元素放在i列
			if ( Place(t) )
			{
				Backtrack( t + 1 );
			}
		}
	}
}

int nQueen( int n )
{
	Queen X;
	//初始化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;
}

void Queen::Backtrack(void)
{
	x[1] = 0;
	int k = 1;
	while( k > 0 )
	{
		x[k] += 1;
		//选中第x[k]列
		while( ( x[k] <= n ) && !( Place(k) ) )
		{
			x[k] += 1;
		}
		if( x[k] <= n )
		{
			if ( k == n  )
			{
				sum++;
			}
			else
			{
				++k;
				x[k] = 0;
			}
		}
		else
		{
			--k;
			//上一行的列继续调整
		}
	}
}
int main()
{
	return 0;
}