一.问题描述

题目如上图所示，在一个n*n的国际象棋棋盘上怎么摆放能使得皇后互相攻击不到（也就是在任意一列、一行、一条对角线上都不存在两个皇后）

二.思路分析

1.DFS

想要解决这个问题，我们可以使用dfs也就是深度优先遍历，深度优先搜索的步骤为先递归到底再回溯上来，顾名思义，dfs是以深度为目标，一条路走到底，直到达到无路可走时，退回到上一步的状态，走其他路回溯上来。
这题我们就可以定义数组当做棋盘，遍历所有位置判断是否可以放置皇后（需要满足任意一列、一行、一条对角线上都不存在两个皇后），在遍历的过程中需要考虑剪枝的情况，减少解题时间复杂度。

三.代码实现与解析

1.分析

首先我们创建完数组模拟棋盘后，先要依据题意，将数组初始化为.

#include <iostream>
const int N = 20;
using namespace std;
char ret[N][N];bool col[N], dg[N], udg[N];//标记列、对角线上是否已经有皇后int n = 0;void dfs(int u);int main()
{cin >> n;for (int i = 0; i < n; i++)for (int m = 0; m < n; m++)ret[i][m] = '.';dfs(0);//dfs算法函数return 0;
}

紧接着就是dfs函数代码的实现逻辑：

void dfs(int u)
{if (u == n){for (int i = 0; i < n; i++){cout << ret[i] << endl;;}cout<< endl;return;}for (int i = 0; i < n; i++){if (!col[i] && !dg[u + i] && !udg[n + i - u]){ret[u][i] = 'Q';col[i] = dg[u + i] = udg[n + i - u] = true;dfs(u + 1);ret[u][i] = '.';col[i] = dg[u + i] = udg[n + i - u] = false;}}
}

需要重点理解的在for循环中i代表的是列数（遍历的是列），u代表的是层数，if判断当行、对角线均暂无皇后时，则可以在此放置皇后，并标识为已经放置，此时这一层的放置就结束了，所以接着就要递归下一层，之后就会分为两种情况：
1.递归到最后一层成功打印了这次的方案。接着就会向上回溯

ret[u][i] = '.';
col[i] = dg[u + i] = udg[n + i - u] = false;

执行恢复逻辑。
2.在后续层数遍历放置时，出现了不合法的情况（列数到达阈值依旧没有放置），此时就会剪枝，也是会回溯到上图代码进行恢复。

2.完整代码

#include <iostream>
const int N = 20;
using namespace std;
char ret[N][N];bool col[N], dg[N], udg[N];int n = 0;void dfs(int u);int main()
{cin >> n;for (int i = 0; i < n; i++)for (int m = 0; m < n; m++)ret[i][m] = '.';dfs(0);return 0;
}
void dfs(int u)
{if (u == n){for (int i = 0; i < n; i++){cout << ret[i] << endl;;}cout<< endl;return;}for (int i = 0; i < n; i++){if (!col[i] && !dg[u + i] && !udg[n + i - u]){ret[u][i] = 'Q';col[i] = dg[u + i] = udg[n + i - u] = true;dfs(u + 1);ret[u][i] = '.';col[i] = dg[u + i] = udg[n + i - u] = false;}}
}