M02754 八皇后

思路：

• 枚举全排列 $p$，表示第 $i$ 行的皇后在第 $p_i$ 列。
• 我们可以用 $i+p_i,i-p_i$ 分别代表某一个皇后所在的左上-右下、左下-右上两条对角线。
• 分别判断有无重复的 $i+p_i,i-p_i$ 即可，笔者通过压位实现。
• 时间复杂度为 $O(N!\cdot N+nN)$，其中 $N=8$。

代码：

#include <iostream>
#include <algorithm>

using namespace std;

int p[9], ans[93][9];

int main(){
	int cnt = 0;
	for (int i = 1; i <= 8; i++){
		p[i] = i;
	}
	do {
		int st1 = 0, st2 = 0;
		bool flag = true;
		for (int i = 1; i <= 8; i++){
			int x = i + p[i], y = i - p[i] + 8;
			if ((st1 >> x & 1) || (st2 >> y & 1)){
				flag = false;
				break;
			}
			st1 |= 1 << x;
			st2 |= 1 << y;
		}
		if (flag){
			cnt++;
			for (int i = 1; i <= 8; i++){
				ans[cnt][i] = p[i];
			}
		}
	} while (next_permutation(p + 1, p + 9));
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++){
		int b;
		cin >> b;
		for (int j = 1; j <= 8; j++){
			cout << ans[b][j];
		}
		cout << endl;
	}
	return 0;
}