思路(字丑勿喷)
类全排列 - 按行枚举 - $O(N!)$
#include <iostream>
using namespace std;
const int N = 20; // 对角线比较多,开两倍
int n;
char board[N][N];
bool col[N], dg[N], udg[N]; // dg 和 udg 分别代表主副对角线, col 为列
void dfs(int u)
{
if (u == n) {
for (int i = 0; i < n; i++) {
puts(board[i]);
}
puts("");
return;
}
// i 为列,u 为行
for (int i = 0; i < n; i++) {
// 剪枝,如果路径冲突则不继续,直接回溯
// n - u + i 是为了保证映射位置非负
if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
board[u][i] = 'Q';
col[i] = dg[u + i] = udg[n - u + i] = true; // 打标记
dfs(u + 1);
// 接下来两步都是恢复现场
col[i] = dg[u + i] = udg[n - u + i] = false;
board[u][i] = '.';
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
dfs(0);
return 0;
}
按格搜索 - 无剪枝 - $O(2^{n^{2}})$
#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];
// s 为皇后数量
void dfs(int x, int y, int s)
{
// 若 y 越界,则拉回开头,到下一行
if (y == n) {
y = 0, x ++ ;
}
// 说明最后一行枚举完毕
if (x == n) {
// 若皇后数量足够
if (s == n) {
for (int i = 0; i < n; i++) {
puts(g[i]);
}
puts("");
}
return; // return 要放在外面,否则会爆内存
}
// 放皇后
dfs(x, y + 1, s);
// 不放皇后
// 行列主副对角线都符合空
if (!row[x] && !col[y] && !dg[y + x] && !udg[y - x + n]) {
g[x][y] = 'Q';
row[x] = col[y] = dg[y + x] = udg[y - x + n] = true;
dfs(x, y + 1, s + 1); // 放一个棋子,搜下一格
row[x] = col[y] = dg[y + x] = udg[y - x + n] = false;
g[x][y] = '.';
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g[i][j] = '.';
}
}
dfs(0, 0, 0); // 从左上角第一个点开始枚举
return 0;
}