本系列所有题目均为Acwing课的内容，发表博客既是为了学习总结，加深自己的印象，同时也是为了以后回过头来看时，不会感叹虚度光阴罢了，因此如果出现错误，欢迎大家能够指出错误，我会认真改正的。同时也希望文章能够让你有所收获，与君共勉！

今天这道题使用深度优先搜索（DFS）进行求解的，当然也是一道很经典的问题。

n皇后问题

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

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

输入格式
共一行，包含整数 n。

输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围
1≤n≤9
输入样例：
4
输出样例：
.Q..
...Q
Q...
..Q.

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

算法原理

第一种方式
经过分析我们可以知道，当某一位置的一行或一列或主对角线或副对角线存在皇后时，该位置就不能放皇后，因此我们可以用排列组合的方法，枚举每一行_ _ _ _选一个位置放皇后，容易知道当枚举到四个位置时说明可以这时候得到的状态一定是目标状态。
这个过程中的剪枝就是对于判断列和主对角线与副对角线是否有皇后，即if( !col[i] && !dg[i] && udg[-x+n+i])，因为我们枚举的就是每一行放皇后的位置，因此不用判断行，udg表示副对角线，副对角线上的元素有相同的b，所以我们可以通过udg来判断在其他位置上有没有皇后，如果有就为True，因为y=x+b这个函数变形一下就得到b=-x+y也就是当前这个位置的副对角线由于可能产生负数，所以我们需要加n，即b = -x+y+n，b可以理解为第几条对角线。
如果满足上述条件，我们就可以在该位置放皇后，并且修改该位置所属列，主对角线，副对角线的状态。并且再一次往下递归，要注意返回的时候我们要把状态修改回来，所以递归下面的代码的作用就是恢复状态，也叫状态回溯。
第二种方式
除了这个方法还有第二种方法，就是按照最原始的搜索方式，因为每个格子只有两种状态，那么我只要找出所有各自的排列组合，其中就一定会有满足要求的解，总归能找到，就能输出他。

代码实现

第一种方式

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 20;

char g[N][N]; // 图
bool col[N], dg[N], udg[N];	// 一个列数组，一个对角线数组，一个反对角线数组
int n;

void DFS(int x) {
	if (x == n) {
		for (int i = 0; i < n; ++i)
			puts(g[i]);
		puts("");
	}
	for (int i = 0; i < n ; ++i)
		if (!col[i] && !dg[x + i] && !udg[-x + i + n]) {
			g[x][i] = 'Q';
			col[i] = dg[x + i] = udg[-x + i + n] = true;
			DFS(x + 1);
			col[i] = dg[x + i] = udg[-x + i + n] = false;
			g[x][i] = '.';
		}
}

int main() {
	cin >> n;
	for (int i = 0; i < n ; ++i) {
		for (int j = 0; j < n ; ++j) {
			g[i][j] = '.';	// 建图
		}
	}
	DFS(0);
	return 0;
}

第二种方式

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 20;

char g[N][N]; // 图
bool row[N], col[N], dg[N ], udg[N];	// 一个列数组，一个对角线数组，一个反对角线数组，
int n;

void DFS(int x, int y, int q) {	// m行，n列，q皇后
	if (q > n)
		return 	; // 如果皇后数量多于n个就返回
	if (y == n) {	// 边界处返回向下走从头开始
		y = 0;
		x++;
	}
	if (x == n) {
		if (q == n) {
			for (int i = 0; i < n; i ++ )
				puts(g[i]);
			puts("");
		}
		return;
	}

	// 后面找出两种状态

	// 不放皇后
	DFS(x, y + 1, q);	// 后面的q>n防止连续放皇后，横着搜索，所以是n+1

	// 放皇后
	if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {	// 如果不满足要求就会自动回溯（函数执行完了）
		g[x][y] = 'Q';
		row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
		// 画个图理解下，相当于原来的第四象限变成了第一象限，m+n表示m行第n条主对角线
		// udg中的m-n+t中-n就相当于副对角线即矩阵右上角，+t将其变成正数，回到了这一行的开头，+m就是当这一行第m个副对角线上
		DFS(x, y + 1, q + 1);	// 放了一个皇后往后走
		g[x][y] = '.';
		row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;	// 依然要回溯状态，当这个皇后走不通时就返回到树的上面
	}
}

int main() {
	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;
}