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

八皇后问题(dfs + 回溯)

程序员文章站 2024-03-12 15:28:56
...

八皇后问题(dfs + 回溯)

八皇后问题(dfs + 回溯)

 

#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;
}

 

相关标签: 机试