N皇后||题解集合
- 回溯法
回溯法
本题就是leetcode 面试题 08.12. 八皇后----回溯篇7，也就是我们回溯篇7中讲过的问题，只不过这里区别在于，第 51 题需要得到所有可能的解，这道题只需要得到可能的解的数量。因此这道题可以使用第 51 题的做法，只需要将得到所有可能的解改成得到可能的解的数量即可。
这里只演示使用回溯篇6中第一种方式的做法,详情可以去看回溯篇6
具体求解过程也不再啰嗦，详情去看回溯篇6
代码:
代码语言：javascript复制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;
}
};
