要求
八皇后问题不多赘述，下面根据回溯法求解出所有可行解
分析
八皇后问题根本也就是全排列问题，直接求解复杂度过高，但如果把n列先固定下来这样就相当于n行的全排列，接下来检验这些排列中是否每两个都不共对角线即可。
但这样的情况还是可以继续优化，比如说，排列的前面几个数字已经不满足不对角，那么就不需要再进行下面的排列，这样就可以退回到上一个数字位
至于回溯法其实就是决策树，每个分叉代表不同的决定，当一个决定失败后就撤回到父节点
代码
#include<iostream>
#include<math.h>
using namespace std;
const int maxn = 100;
int n, cnt = 0, P[maxn];
bool hashTable[maxn] = { false };
void generateP(int index) {
if (index == n + 1) {
for (int i = 1; i <= n; i++) {
cout << P[i];
}
cout << endl;
cnt++;
return;
}
for (int x = 1; x <= n; x++) {
if (hashTable[x] == false) {
bool flag = true;
for (int pre = 1; pre < index; pre++) {
if (abs(index - pre) == abs(x - P[pre])) {
flag = false;
break;
}
}
if (flag) {
P[index] = x;
hashTable[x] = true;
generateP(index + 1);
hashTable[x] = false;
}
}
}
}
int main() {
n = 8;
generateP(1);
cout << cnt;
return 0;
}
