八皇后问题(dfs + 回溯)
程序员文章站
2024-03-12 15:28:56
...
#include <iostream>
#include <cstdlib>
using namespace std;
int col[9]; // 下标:1 ~ 8行; 内容:放到了哪一列
bool mark [9]; // 这一列是否安排好
int cnt = 0;
void print() {
for (int i = 1; i <= 8; i ++) {
cout << col[i] << " ";
}
cout << endl;
return ;
}
// 第K行已经安排好了 在col[K]
bool isDanger(int k) {
for (int i = 1; i <= k - 1; i ++) {
// 有人已经在这一列了,冲突
if (col[i] == col[k]) {
return true;
} else if (i + col[i] == k + col[k]) {
return true;
} else if (i - col[i] == k - col[k]) {
return true;
}
}
return 0;
}
void dfs(int index) {
if (index == 9) {
print();
cnt++;
return ;
}
for (int i = 1; i <= 8; i++) {
if (mark[i] == 0) {
col[index] = i;
if (isDanger(index)) {
continue;
} else {
mark[i] = 1;
dfs(index + 1);
mark[i] = 0;
}
}
}
}
int main() {
for (int i = 0; i <= 8; i++) {
mark[i] = 0;
}
cnt = 0;
dfs(1);
cout << cnt;
}