n-皇后问题
n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
1_597ec77c49-8-queens.png
现在给定整数n,请你输出所有的满足条件的棋子摆法。
输入格式
共一行,包含整数n。
输出格式
每个解决方案占n行,每行输出一个长度为n的字符串,用来表示完整的棋盘状态。
其中”.”表示某一个位置的方格状态为空,”Q”表示某一个位置的方格上摆着皇后。
每个方案输出完成后,输出一个空行。
输出方案的顺序任意,只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例:
4
输出样例:
.Q..
…Q
Q…
..Q.
..Q.
Q…
…Q
.Q..
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
/*
推荐使用 行号 作为dfs的参数,过度方便,范围明确;
切换搜索范围时候需要恢复现场;
实现细节:
1. 输出使用puts,每次输出一行,速度略快于printf;
2. 为配合 puts函数 的使用,需要初始化的时候适当添加'\0';
*/
// 可能性数量;
const int CNT = 20;
int n;
/*
row:当前行是否被占用;
col:当前列是否被占用;
rhDiag:右上角高的对角线——主对角线;
lhDiag:左边高的对角线——次对角线;
*/
bool row[CNT], col[CNT], rhDiag[CNT], lhDiag[CNT];
// brd 即 board,棋盘;
char brd[CNT][CNT];
/*
—— 行数 适合向下一个状态转换, 下一行 r+1 即可;
但是若使用点坐标就会非常麻烦;
—— 每一行都对应一个 深度搜索树
*/
void dfs(int r) {
if (r == n) {
for (int i = 0; i < n; i++) {
puts(brd[i]);
}
puts("");
return;
}
for (int i = 0; i < n; i++) {
if (!row[r] && !col[i] && !rhDiag[r + i] && !lhDiag[r - i + n]) {
row[r] = col[i] = rhDiag[r + i] = lhDiag[r - i + n] = true;
brd[r][i] = 'Q';
dfs(r + 1);
// dfs之后,该搜索树结束;
// 开启新的搜索树,需要恢复现场;
row[r] = col[i] = rhDiag[r + i] = lhDiag[r - i + n] = false;
brd[r][i] = '.';
}
}
}
int main() {
cin >> n;
memset(brd, '.', sizeof(brd));
for (int i = 0; i < n; i++){
brd[i][n] = '\0';
}
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(row));
memset(rhDiag, 0, sizeof(row));
memset(lhDiag, 0, sizeof(row));
dfs(0);
return 0;
}