leetcode 52. N皇后 II----回溯篇8

class Solution 
{
	int sum = 0;
	vector<int> a; //用一个一维数组a来表示每个皇后的位置，a[2] = 4表示皇后的位置位于a(2, 4), 即二行四列上
public:
		int totalNQueens(int n) 
		{
			backTrace(0, n);
			return sum;
		}
	void backTrace(int n, int N)
	{
		if (n == N)//最后一个皇后放置完毕
			sum++;
		else
		{
			//对每一列进行试探
			for (int i = 0; i < N; i++)
			{
				//将当前皇后放置在第n行，第i列上
				a.push_back(i);
				//如果当前n行i列能够放置皇后，那么就继续寻找下一个皇后的合适放置位置
				if (isValild(n))
					backTrace(n + 1, N);
				//如果找到了一种解，或者当前状态无解，那么恢复到上一层的状态，去寻找其他可能解
				a.pop_back();

			}
		}
	}
	bool isValild(int n)//这里n是正在放置第几个皇后，也可以理解为正在第几行放置皇后
	{
		//第n行要放置的皇后需要和前面n-1行已经放置的皇后进行检查，看是否产生位置冲突
		for (int i = 0; i < n; i++)
		{
			if (a[n] == a[i] || abs(a[n] - a[i]) == abs(n - i))
				return false;
		}
		return true;
	}
};