【C++板块提升计划】N皇后---含代码，详细讲解【原创】
本帖最后由 zhangjinxuan 于 2023-1-9 14:26 编辑鱼油们好，今天我来分享一下N皇后的解法
题目简介：
在一个 n×n 的棋盘中一行一行地放入 n 个皇后，要求皇后之间不能互相攻击，请按字典序从小到大的顺序输出所有的方案。
一个皇后能攻击和她同一行、同一列、同一斜线上的所有其他格子上的棋子。
输入格式：
一行一个整数 n。
输出格式：
按字典序从小到大的顺序一行一行输出所有方案，每行一组方案，输出 n 个整数，依次表示第 1,2,…,n 行的皇后在第几列。
样例输入：
6
样例输出：
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
5 3 1 6 4 2
数据范围：3 <= n <= 13
这是一道经典的深搜（DFS)题，USACO可是考过的，所以一定要学会！
思路和代码：
1：我们先把框架写好，一些头文件、命名空间、main先写好，这步很简单，不多讲：
#include <cstdio>
using namespace std;
int main() {
return 0;
}
2:定义所需变量，首先，n要定义，以及棋盘布局queen二维数组，以及一些深搜要用的数组，另外，可以用个宏变量MAXS方便以后调试程序:
#define MAXS 13
int n;
bool queen, col, left, right;
有人说，这那么多bool数组用来干啥的？
其实queen是来对之后的输出做准备的，而col是来查看第i列有没有皇后，left,right表示第i个斜线有没有皇后，left表示左斜线，right表示右斜线，一个矩阵是有n*2-1条斜线，具体怎么表示就详细看后面
Q:为什么只用记列号,而不记行号呢？
A:因为我们是一行一行放置皇后的（题面说了的），放完第一行放下一行，放完第i行放i+1行，第i行的皇后不可能和其它行的皇后有行的冲突吧，所以不记行号，还是不理解可以在后面的代码中体会到的
3.1:声明深搜函数：
void dfs(int row);
先声明，无需返回值，写void,后面的row代表行号，表示当前要在第row行放置皇后
3.2：定义函数，并且判断边界条件：
如果r>n，说明所有皇后放置完毕，打印结果
void dfs(int r) {
if (r > n) {
for (int i = 1; i <= n; ++i) //遍历queen布尔数组
for (int j = 1; j <= n; ++j)
if (queen) { //如果当前位置有皇后
printf("%d ", j); //打印第i行皇后的列号 注，第二位才是列号
break; //可以break了
}
puts("");//打印换行
return; //必须返回，否则会陷入死递归
}
}
注释里有讲，这里不赘述，关于queen布尔数组看3.3步
3.3检查第i行j列的皇后（难点之难点）：
检查是否可以放置皇后：
for (int c = 1; c <= n; ++c) { //枚举列号
if (!col && !left && !right) { //判断是否可以放置
//...
}
}
Q:这些col、left和right是什么意思？干嘛要写我不认识他，他又不认识我的判断呢？
A:正是我要讲的，也是难点之一，首先col不用讲，就是判断该列有没有皇后，而left,right是判断斜行，这个只能找规律，规律如下：
首先，我们画一个矩阵（简单起见，画4*4）：
[ ][ ][ ][ ]
[ ][ ][ ][ ]
[ ][ ][ ][ ]
[ ][ ][ ][ ]
标上行号列号：
1234
1 [ ][ ][ ][ ]
2 [ ][ ][ ][ ]
3 [ ][ ][ ][ ]
4 [ ][ ][ ][ ]
我们可以发现，在同一个左斜行，每个点的行号列号之和是相等的，我们来看看：
1 2 3 4
1 [ ] [ ] [ ]
2 [ ] [ ] [ ]
3 [ ] [ ] [ ]
4 [ ] [ ] [ ] [ ]
Q1行号列号和是4，Q2也是4，Q3也是4
所以我们可以通过这个特性来得出left的代码
那么，对于右斜行，我们可以把行号数字，或者列号数字翻转过来(n+1-号,且只能反转一个，都是一样的):
4321
1 [ ][ ][ ][ ]
2 [ ][ ][ ][ ]
3 [ ][ ][ ][ ]
4 [ ][ ][ ][ ]
再来看看右斜行列行号之和是否相等：
4 3 2 1
1 [ ] [ ] [ ]
2 [ ] [ ] [ ]
3 [ ] [ ] [ ]
4 [ ] [ ] [ ]
可以发现，他们的和都是5，所以我们也得出了right的代码
Q:那为什么中间要加一呢？
A:主要是方便大家理解，不然矩阵就长这样了：
3210
1 [ ][ ][ ][ ]
2 [ ][ ][ ][ ]
3 [ ][ ][ ][ ]
4 [ ][ ][ ][ ]
这样理解肯定不方便
如果这步不理解，可以自己定义一个check函数，检查列号斜行（就像小甲鱼那样)
3.4放置递归并回溯（重点之重点）：
先设置好该位置存在皇后:
queen = col = left = right = true;
再递归下一行：
dfs(r + 1);
回溯，清除状态：
queen = col = left = right = false;
好了，至此，最难的部分已经完成了，接下来就是输入，调用部分啦
4.输入并调用：
scanf("%d", &n);
dfs(1);
这里一定要传入第一行，传入其他数字会发生奇奇怪怪的结果
全部代码：
#include <cstdio>
using namespace std;
#define MAXS 13
int n, cnt;
bool queen, col, left, right;
void dfs(int r) {
if (r > n) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (queen) {
printf("%d ", j);
break;
}
puts("");
++cnt;
return;
}
for (int c = 1; c <= n; ++c) {
if (!col && !left && !right) {
queen = col = left = right = true;
dfs(r + 1);
queen = col = left = right = false;
}
}
}
int main() {
scanf("%d", &n);
dfs(1);
//printf("%d", cnt);
return 0;
}
总结：还是比较简单，之后可能有变种之类的，大家尽量学会！
[如果有帮助，别忘了小小的评分，一个荣誉也是爱~]
说明：本文为本萌新原创，如有雷同，纯属巧合！ @高山 @元豪 来看贴吖{:10_256:} zhangjinxuan 发表于 2022-9-23 21:14
@高山 @元豪 来看贴吖
来啦~~{:5_109:} {:10_256:}{:10_256:} zhangjinxuan 发表于 2022-9-23 21:14
@高山 @元豪 来看贴吖
N 皇后问题
当年的痛啊 写的不错啊 （虽然回帖觉奖励有点小）
技术不错 高山 发表于 2022-9-23 21:56
（虽然回帖觉奖励有点小）
技术不错
感谢支持 奖励 hveagle 发表于 2022-9-24 07:06
奖励
别顾着奖励啊，看一看呗{:10_256:} zhangjinxuan 发表于 2022-9-24 07:34
别顾着奖励啊，看一看呗
看了 lz写的很详细呀！赞{:10_275:} 一点点儿 发表于 2022-9-24 11:58
lz写的很详细呀！赞
回帖奖励无了，又变冷清了 em，不错不错！！！！！！！ zhangjinxuan 发表于 2022-9-24 12:08
回帖奖励无了，又变冷清了
送你点鱼币发回帖奖励，详见评分（共8，把我今天的评分次数都用完了） 高山 发表于 2022-9-24 14:09
送你点鱼币发回帖奖励，详见评分（共8，把我今天的评分次数都用完了）
待会再搞，现在要写作业 回帖奖励{:10_254:} {:5_108:} 是个好话题，有空来研究下 {:10_256:}{:10_256:}{:10_256:}厉害
页:
[1]
2