八皇后

链接

N皇后问题,指的是在n * n 的棋盘上,放置n个皇后,使她们互相不能攻击的解法有多少种

皇后走法汇集了车和象的能力,走法极其灵活,我们需要使她们不能在同一行,同一列,同意斜线

由于要求所有解法,我们需要穷举

不妨从上到下,依次穷举,设一个数组visit,表示第i列已经被占了,这样可以保证每一列只有一个皇后。再设两个map容器fir和sec,分别表示从左上到右下和右上到左下的斜线

不难发现,同一斜线的截距相同,我们根据这一规律,可以保证一个斜线只有一个皇后

题目要求字典序排列前三个答案,不过我们这种方法已经是字典序了,所以不用管

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
void dfs(int& end,int dep,int& count,vector<int>&ans,int n,vector<bool>&visit,unordered_map<int,bool>&mp_fir,unordered_map<int,bool>&mp_sec) {
	if (ans.size() == n) {
		if (end < 3) {
			for (int num : ans) {
				cout << num << " ";
			}
			cout << endl;
		}
		count++;
		end++;
		return;
	}
	for (int i = 0;i < n;i++) {
		if (!visit[i]&&!mp_fir[i+dep]&&!mp_sec[i-dep]) {
			visit[i] = 1;
			mp_fir[i + dep] = 1;
			mp_sec[i - dep] = 1;
			ans.push_back(i + 1);
			dfs(end, dep + 1, count, ans, n, visit, mp_fir, mp_sec);
			visit[i] = 0;
			mp_fir[i + dep] = 0;
			mp_sec[i - dep] = 0;
			ans.pop_back();
		}
		
	}
}
int main() {
	int n;
	cin >> n;
	vector<bool>visit(n,0);
	unordered_map<int, bool>mp_fir,mp_sec;
	vector<int>ans;
	int count = 0;
	int end = 0;
	dfs(end, 0, count, ans, n, visit, mp_fir, mp_sec);
	cout << count;
}

时间复杂度:O(n!)

空间复杂度:O(n)