求八皇后的解的个数
程序员文章站
2022-05-25 11:48:41
...
用DFS(深度优先搜索的方法)。
ans | 解的个数 |
col | 代表某一列是否被占用 |
x1 |
代表正斜率对角线是否被占用 |
x2 | 代表负斜率对角线是否被占用 |
check( int r,int i )函数 | 检查第r行第i列是否可以被占用 |
#include <iostream>
using namespace std;
int ans = 0; //解的个数
bool col[10], x1[20], x2[20]; //col某一列是否被占用,x1正斜线是否被占用,x2负斜线是否被占用。
bool check(int r, int i) {
return !col[i] && !x1[r+i] && !x2[r-i+8]; //第r行第i列,列没有占用,两个斜方向也没有占用,则返回正确。否则返回不能放置。
}
void dfs(int r) {
if (r == 8) { //递归出口
ans++;
return;
}
for(int i = 0; i < 8; i++) { //遍历位置,第r个棋子放置在8个中的哪一个位置。
if(check(r, i)) {
col[i] = x1[r+i] = x2[r - i + 8] = true; //列,2个斜方向标记
dfs(r + 1);
col[i] = x1[r + i] = x2[r - i + 8] = false; //因为要求所有情况,要取消标记
}
}
}
int main() {
dfs(0);
cout << ans << endl;
return 0;
}
得出的答案为(92)