要求
八皇后問題不多贅述碍讨，下面根據(jù)回溯法求解出所有可行解
分析
八皇后問題根本也就是全排列問題独泞，直接求解復(fù)雜度過高亥至，但如果把n列先固定下來這樣就相當(dāng)于n行的全排列兆览，接下來檢驗(yàn)這些排列中是否每兩個(gè)都不共對(duì)角線即可屈溉。
但這樣的情況還是可以繼續(xù)優(yōu)化，比如說拓颓，排列的前面幾個(gè)數(shù)字已經(jīng)不滿足不對(duì)角语婴，那么就不需要再進(jìn)行下面的排列跳纳，這樣就可以退回到上一個(gè)數(shù)字位
至于回溯法其實(shí)就是決策樹首有，每個(gè)分叉代表不同的決定，當(dāng)一個(gè)決定失敗后就撤回到父節(jié)點(diǎ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;
}
