八皇后问题
原题描述
n?皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 n，请你输出所有的满足条件的棋子摆法。
输入格式
共一行，包含整数 n。
输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
注意：行末不能有多余空格。
输出方案的顺序任意，只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例：
4
输出样例：
.Q…
…Q
Q…
…Q.
…Q.
Q…
…Q
.Q…
参考代码(C++版本)
#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N]; //存放题目所需的棋盘
bool col[N],dg[N],udg[N];//记录当前列，当前正对角线，当前反对角线的状态是探测过与否
void dfs(int u)
{
//到达递归结束的边界 输出当前放置好皇后的地图
if(u == n)
{
for(int i = 0;i < n;i++) puts(g[i]);
puts("");
return;//不要忘记return,否则会无休止的运行
}
//尝试每一种可能
for(int i = 0;i < n;i++)
{
//判断横行u和竖列i组成的坐标(u,i) 在这列，在这正对角线，在这反对角线中是否放置了皇后
if(!col[i] && !dg[u+i] && !udg[n-u+i])
{
g[u][i] = 'Q';
col[i] = dg[u+i] = udg[n-u+i] = true;//标记这个放过皇后的点
dfs(u+1);//继续到下一个位置
col[i] = dg[u+i] = udg[n-u+i] = false;//回溯回来的时候，恢复现场
g[u][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;
}
问题剖析
八皇后的核心是将每个位置逐一试探，保证每个皇后不在同一行，不在同一列，不在同一正对角线，不在同一反对角线。逐一试探的过程其实就是深度优先遍历dfs的过程，我们只用梳理好当前这个位置试探的逻辑，对于下一个位置，则和当前这一步的逻辑一样
逐步解析
处理输入
cin >> n;
//创建地图
for(int i = 0;i < n;i++)
for(int j = 0; j < n;j++) g[i][j] = '.';
放置深搜起点
dfs(0);//起点是可以随意的，不影响结果
编写核心函数——void dfs(int u)
- 判断边界——已经尝试完所有可能，输出放置的皇后次序
if(u == n)
{
for(int i = 0;i < n;i++) puts(g[i]);
puts("");
return;
}
- 对每一个位置进行尝试
for(int i = 0;i < n;i++)
- 剪枝
//剪枝，就是减小搜索树规模、尽早排除搜索树中不必要的分支的一种手段。
if(!col[i] && !dg[u+i] && !udg[n-u+i])
剪枝的逻辑借助一元一次方程组，整个棋盘可以抽象为一个坐标轴。u是传入的参数，类比为一元方程组的x,i则是在不断迭代的，是可以类比为因为截距b变化而变化的y。那么正对角线和反对角线就是斜率为-1的方程
所以可模拟出:
正对角线的方程为i = -1 * u + b,则b = u+i
反对角线的方程为i = 1 * u + b,则b = i-u,因为要作为数组的参数，不能为负数，所以考虑加一个偏移量n，保证参数为正。
为什么可以这种模拟？如图：
虽然u和i的值在不断变化，但是总和是不变的，因此会形成两条正反对角线。对于相减可能为负的情况，添加偏移量n。所以就可以用这种方式来搜素各个位置的状态。
- 放置皇后，标记当前位置
g[u][i] = 'Q';
col[i] = dg[u+i] = udg[n-u+i] = true;
- 继续到下一步
dfs(u+1);
- 恢复现场
col[i] = dg[u+i] = udg[n-u+i] = false;
g[u][i] = '.';