一、引入
n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、
同一列或同一斜线上。现在给定整数n，请你输出所有的满足条件的棋子摆法。
输入格式
共一行，包含整数n。
输出格式
每个解决方案占n行，每行输出一个长度为n的字符串，用来表示完整的棋盘状态。
其中”.”表示某一个位置的方格状态为空，”Q”表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
数据范围
1≤n≤9
输入样例：
4
输出样例：
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
二、剪枝
我们一行一行的尝试在某个位置放置一个皇后，然后检查这个位置是否能放皇后，若果不能放就直接选择下一个位置，不让搜索树继续往下发展。 若该位置能放，才继续往下发展放其他的皇后。
判断该位置上是否可以放该皇后： col【】数组记录某列已经放过了皇后。col【i】= 1代表第i列已经放了一个皇后。 d【】 数组来记录某正对角线已经放置过了皇后。 ud【】数组来记录某反对角线已经放置过了皇后。
正对角线：
反对角线：
三、代码实现
#include <cstdio>
const int N
= 20;
char g
[N
][N
];
int n
, col
[N
], d
[N
], ud
[N
];
bool check(int x
, int y
) {
if (col
[y
] || d
[x
+ y
] || ud
[n
- x
+ y
]) return false;
return true;
}
void dfs(int row
) {
if (row
== n
) {
for (int i
= 0; i
< n
; i
++) printf("%s\n", g
[i
]);
printf("\n");
return;
}
for (int i
= 0; i
< n
; i
++) {
int x
= row
, y
= i
;
if (check(x
, y
)) {
col
[y
] = d
[x
+ y
] = ud
[n
- x
+ y
] = 1;
g
[x
][y
] = 'Q';
dfs(row
+ 1);
g
[x
][y
] = '.';
col
[y
] = d
[x
+ y
] = ud
[n
- x
+ y
] = 0;
}
}
}
int main() {
scanf("%d", &n
);
for (int i
= 0; i
< n
; i
++) {
for (int j
= 0; j
< n
; j
++) {
g
[i
][j
] = '.';
}
}
dfs(0);
return 0;
}
