深度优先搜索解决八皇后问题
八皇后问题是什么：
题解：
#include<iostream>
#include<math.h>
using namespace std;
int a[9] = {
0};
int count = 0;
bool canPlace(int step, int pos) {
for(int i = 1; i < step; i++) {
if(a[i] == pos || abs(a[i] - pos) == abs(step-i))
return false;
}
return true;
}
void dfs(int step) {
if(step == 9) {
for (int i = 1; i <= 8; i++)
printf("%d ", a[i]);
printf("
");
count++;
return;
}
for(int i = 1; i <= 8; i++) {
if(canPlace(step, i)) {
a[step] = i;
dfs(step+1);
a[step] = 0;
}
}
}
int main() {
dfs(1);
printf("%d", count);
}
解析： 数组a记录棋子摆放位置，例如a[3] = 5表示在第三的第五格放了棋子，任意两个皇后都同一斜线上，意味着(a[step]-a[i])/(step-i) 的绝对值不能是1，同一列好理解，a[step] != a[i]，同一行不用考虑，因为我们一行只放一个棋子。
上一篇：
IDEA上Java项目控制台中文乱码