heihei12305

回溯法有“通用的解题法”之称，用它可以系统的搜索一个问题的所有解或任一解。

回溯法是一个既带有系统性又带有跳跃性的搜索算法

回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，
解为叶子节点。搜索过程中每到达一个结点，就判断该节点为根的子树是否含有问题的解，
如果确定不含有问题的解，则放弃对该子树的搜索，退回到上层父节点，继续下一步深度优先搜索过程


问题描述:在n*n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋规则，皇后可以攻击与之处在同一行或者同一列斜线上的棋子。n后问题等价于在n*n格的棋盘上放置n个皇后，任何2个皇后不放在同一行
或同一列或同一斜线上。


用n元组x[1:n]表示n后问题的解.其中，x[i]表示皇后i放在棋盘第i行的第x[i]列，由于不允许将2个皇后放置同一列上，所以解向量的x[i]互不相同，可将2个皇后不能放在同意斜线上显约束条件=》（i，j）与（k,l）满足 |i-k| != |j-l|

class Queen{
	private:
		bool Place(int k);
		void Backtrack(int t);
		int n;//皇后个数
		vector<int> x;//当前解
		long sum;//当前已找到的可行方案数
};
boll Queen::Place(int k)
{
	for(int i = 1;i<k;i++)
	{
		if((abs(k-i)==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++)
		{
			x[t] = i;
			if(Place(t))
				Backtrack(t+1);
		}
}
int nQueen(int n)
{
	Queen X;//初始化x
	X.n = n;
	X.sum = 0;
	vector<int>  p(n+1,0)
	X.x = p;
	X.Backtrack(1);
	delete[] p;
	return X.sum;
}