【C++板块提升计划】N皇后---含代码，详细讲解【原创】

zhangjinxuan

鱼油们好，今天我来分享一下N皇后的解法

题目简介：
在一个 n×n 的棋盘中一行一行地放入 n 个皇后，要求皇后之间不能互相攻击，请按字典序从小到大的顺序输出所有的方案。
一个皇后能攻击和她同一行、同一列、同一斜线上的所有其他格子上的棋子。

输入格式：
一行一个整数 n。

输出格式：
按字典序从小到大的顺序一行一行输出所有方案，每行一组方案，输出 n 个整数，依次表示第 1,2,…,n 行的皇后在第几列。

样例输入：

1. 6

复制代码

样例输出：

1. 2 4 6 1 3 5
   
2. 3 6 2 5 1 4
   
3. 4 1 5 2 6 3
   
4. 5 3 1 6 4 2

复制代码

数据范围：3 <= n <= 13

这是一道经典的深搜（DFS)题，USACO可是考过的，所以一定要学会！

思路和代码：
1：我们先把框架写好，一些头文件、命名空间、main先写好，这步很简单，不多讲：

1. #include <cstdio>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int main() {
   
6.         return 0;
   
7. }

复制代码

2:定义所需变量，首先，n要定义，以及棋盘布局queen二维数组，以及一些深搜要用的数组，另外，可以用个宏变量MAXS方便以后调试程序:

1. #define MAXS 13
   
2. 
   
3. int n;
   
4. bool queen[MAXS + 1][MAXS + 1], col[MAXS + 1], left[MAXS * 2 + 2], right[MAXS * 2 + 2];
   

复制代码

有人说，这那么多bool数组用来干啥的？

其实queen是来对之后的输出做准备的，而col是来查看第i列有没有皇后，left,right表示第i个斜线有没有皇后，left表示左斜线，right表示右斜线，一个矩阵是有n*2-1条斜线，具体怎么表示就详细看后面

Q:为什么只用记列号,而不记行号呢？
A:因为我们是一行一行放置皇后的（题面说了的），放完第一行放下一行，放完第i行放i+1行，第i行的皇后不可能和其它行的皇后有行的冲突吧，所以不记行号，还是不理解可以在后面的代码中体会到的

3.1:声明深搜函数：

1. void dfs(int row);

复制代码

先声明，无需返回值，写void,后面的row代表行号，表示当前要在第row行放置皇后

3.2：定义函数，并且判断边界条件：
如果r>n，说明所有皇后放置完毕，打印结果

1. void dfs(int r) {
   
2.         if (r > n) {
   
3.                 for (int i = 1; i <= n; ++i) //遍历queen布尔数组
   
4.                         for (int j = 1; j <= n; ++j)
   
5.                                 if (queen[i][j]) { //如果当前位置有皇后
   
6.                                         printf("%d ", j); //打印第i行皇后的列号 注，第二位才是列号
   
7.                                         break; //可以break了
   
8.                                 }
   
9.                 puts("");//打印换行
   
10.                 return; //必须返回，否则会陷入死递归
    
11.         }
    
12. }

复制代码

注释里有讲，这里不赘述，关于queen布尔数组看3.3步

3.3检查第i行j列的皇后（难点之难点）：
检查是否可以放置皇后：

1. for (int c = 1; c <= n; ++c) { //枚举列号
   
2.                 if (!col[c] && !left[c + r] && !right[c + n + 1 - r]) { //判断是否可以放置
   
3.                                 //...
   
4.                 }
   
5.         }

复制代码

Q:这些col[c]、left[c + r]和right[c + n + 1 - r]是什么意思？干嘛要写我不认识他，他又不认识我的判断呢？
A:正是我要讲的，也是难点之一，首先col[c]不用讲，就是判断该列有没有皇后，而left,right是判断斜行，这个只能找规律，规律如下：

首先，我们画一个矩阵（简单起见，画4*4）：

[ ][ ][ ][ ]
[ ][ ][ ][ ]
[ ][ ][ ][ ]
[ ][ ][ ][ ]

标上行号列号：
   1  2  3  4
1 [ ][ ][ ][ ]
2 [ ][ ][ ][ ]
3 [ ][ ][ ][ ]
4 [ ][ ][ ][ ]

我们可以发现，在同一个左斜行，每个点的行号列号之和是相等的，我们来看看：
   1     2      3     4
1 [ ]   [ ]    [Q1] [ ]
2 [ ]   [Q2] [ ]    [ ]
3 [Q3][ ]    [ ]    [ ]
4 [ ]   [ ]    [ ]    [ ]

Q1行号列号和是4，Q2也是4，Q3也是4

所以我们可以通过这个特性来得出left[c + r]的代码

那么，对于右斜行，我们可以把行号数字，或者列号数字翻转过来(n+1-号,且只能反转一个，都是一样的):
   4  3  2  1
1 [ ][ ][ ][ ]
2 [ ][ ][ ][ ]
3 [ ][ ][ ][ ]
4 [ ][ ][ ][ ]

再来看看右斜行列行号之和是否相等：
   4     3      2      1
1 [Q1][ ]    [ ]    [ ]
2 [ ]   [Q2] [ ]    [ ]
3 [ ]   [ ]    [Q3] [ ]
4 [ ]   [ ]    [ ]    [Q4]
可以发现，他们的和都是5，所以我们也得出了right[c + n + 1 - r]的代码

Q:那为什么中间要加一呢？
A:主要是方便大家理解，不然矩阵就长这样了：
   3  2  1  0
1 [ ][ ][ ][ ]
2 [ ][ ][ ][ ]
3 [ ][ ][ ][ ]
4 [ ][ ][ ][ ]
这样理解肯定不方便

如果这步不理解，可以自己定义一个check函数，检查列号斜行（就像小甲鱼那样)

3.4放置递归并回溯（重点之重点）：
先设置好该位置存在皇后:

1. queen[r][c] = col[c] = left[c + r] = right[c + n + 1 - r] = true;

复制代码

再递归下一行：

1. dfs(r + 1);

复制代码

回溯，清除状态：

1. queen[r][c] = col[c] = left[c + r] = right[c + n + 1 - r] = false;

复制代码

好了，至此，最难的部分已经完成了，接下来就是输入，调用部分啦

4.输入并调用：

1. scanf("%d", &n);
   
2. dfs(1);

复制代码

这里一定要传入第一行，传入其他数字会发生奇奇怪怪的结果

全部代码：

1. #include <cstdio>
   
2. 
   
3. using namespace std;
   
4. 
   
5. #define MAXS 13
   
6. 
   
7. int n, cnt;
   
8. bool queen[MAXS + 1][MAXS + 1], col[MAXS + 1], left[MAXS * 2 + 2], right[MAXS * 2 + 2];
   
9. 
   
10. void dfs(int r) {
    
11.         if (r > n) {
    
12.                 for (int i = 1; i <= n; ++i)
    
13.                         for (int j = 1; j <= n; ++j)
    
14.                                 if (queen[i][j]) {
    
15.                                         printf("%d ", j);
    
16.                                         break;
    
17.                                 }
    
18.                 puts("");
    
19.                 ++cnt;
    
20.                 return;
    
21.         }
    
22.         for (int c = 1; c <= n; ++c) {
    
23.                 if (!col[c] && !left[c + r] && !right[c + n + 1 - r]) {
    
24.                         queen[r][c] = col[c] = left[c + r] = right[c + n + 1 - r] = true;
    
25.                         dfs(r + 1);
    
26.                         queen[r][c] = col[c] = left[c + r] = right[c + n + 1 - r] = false;
    
27.                 }
    
28.         }
    
29. }
    
30. 
    
31. int main() {
    
32.         scanf("%d", &n);
    
33.         dfs(1);
    
34.         //printf("%d", cnt);
    
35.         return 0;
    
36. }

复制代码

总结：还是比较简单，之后可能有变种之类的，大家尽量学会！

[如果有帮助，别忘了小小的评分，一个荣誉也是爱~]

说明：本文为本萌新原创，如有雷同，纯属巧合！

zhangjinxuan

@高山 @元豪 来看贴吖

元豪

zhangjinxuan 发表于 2022-9-23 21:14
@高山 @元豪 来看贴吖

来啦~~

元豪

柿子饼同学

zhangjinxuan 发表于 2022-9-23 21:14
@高山 @元豪 来看贴吖

N 皇后问题
当年的痛啊

高山

写的不错啊

高山

（虽然回帖觉奖励有点小）
技术不错

zhangjinxuan

高山 发表于 2022-9-23 21:56
（虽然回帖觉奖励有点小）
技术不错

感谢支持

hveagle

奖励

zhangjinxuan

hveagle 发表于 2022-9-24 07:06
奖励

别顾着奖励啊，看一看呗

hveagle

zhangjinxuan 发表于 2022-9-24 07:34
别顾着奖励啊，看一看呗

看了

一点点儿

lz写的很详细呀！赞

zhangjinxuan

一点点儿 发表于 2022-9-24 11:58
lz写的很详细呀！赞

回帖奖励无了，又变冷清了

高山

em，不错不错！！！！！！！

高山

zhangjinxuan 发表于 2022-9-24 12:08
回帖奖励无了，又变冷清了

送你点鱼币发回帖奖励，详见评分（共8，把我今天的评分次数都用完了）

zhangjinxuan

高山 发表于 2022-9-24 14:09
送你点鱼币发回帖奖励，详见评分（共8，把我今天的评分次数都用完了）

待会再搞，现在要写作业

fishc.love

回帖奖励

hornwong

ROZE

是个好话题，有空来研究下

kerln888

厉害