规则

每一行，每一列，每一上对角线和下对角线都只能放一个皇后。

题目

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入样例：

4

输出样例：

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

注意点

如何利用行号和列号确定是哪条对角线？

上对角线

判断一条对角线上元素之间的联系，上对角线上的每一个元素的行号减去列号是相等的

y=x+b,   b=y-x,凡是在这条线上的相加都等于b，由于棋盘的坐标变化和坐标轴不同，这里大概理解一下含义，同时为了避免负数的存在，则加上n（棋盘的大小）。

下对角线

思路

每个行搜索一个元素，直到搜索完每一行后进行输出，即深度优先搜索。

在第一行任意选取一个数，然后做标记，即给第二行的选择限定了条件，依次往下搜索。

如果不满足条件，就无法执行dfs(u+1),也就无法再深入搜索，最后输出满足深度要求的答案。

代码

#include<iostream>
using namespace std;
const int N = 20;
int n;
char chess[N][N];
bool col[N],dg[2*N],udg[2*N]; //列，上对角线，下对角线   行号-列号+n    行号+列号 //初始化棋盘
void init(){for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)chess[i][j] = '.';
}void dfs(int u){//不满足列或对角线的条件if(u > n){for(int i = 1; i <=n; i++){for(int j = 1; j <= n; j++)cout << chess[i][j] << " ";cout << endl;}cout << endl;return;}	for(int i = 1; i <= n; i++){if(!col[i] && !dg[n+u-i] && !udg[u+i-1]){chess[u][i] = 'Q';col[i] =dg[n+u-i]= udg[u+i-1] =  true;dfs(u+1);//恢复现场col[i] =dg[n+u-i]= udg[u+i-1] =  false;chess[u][i] = '.';}}
}int main(){cin >> n;init();dfs(1);	
}