欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求八皇后的解的个数

程序员文章站 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

相关标签: 八皇后