漫画：什么是八皇后问题？

ゝ一纸荒年。 2023-07-12 11:51 31阅读 0赞

![format_png][]

![format_png 1][]

**—————  第二天  —————**

![format_png 2][]

![format_png 3][]

![format_png 4][]

题目是什么意思呢？

国际象棋中的皇后，可以横向、纵向、斜向移动。如何在一个8X8的棋盘上放置8个皇后，使得**任意两个皇后都不在同一条横线、竖线、斜线方向上**？

让我们来举个栗子，下图的绿色格子是一个皇后在棋盘上的“封锁范围”，其他皇后不得放置在这些格子：

![format_png 5][]

下图的绿色格子是两个皇后在棋盘上的“封锁范围”，其他皇后不得放置在这些格子：

![format_png 6][]

那么，如何遵循规则，同时放置这8个皇后呢？让我们来看看小灰的回答。

![format_png 7][]

![format_png 8][]

————————————

![format_png 9][]

![format_png 10][]

![format_png 11][]

![format_png 12][]

**什么是八皇后问题？**

八皇后问题是一个古老的问题，于1848年由一位国际象棋棋手提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，如何求解？

以高斯为代表的许多数学家先后研究过这个问题。后来，当计算机问世，通过计算机程序的运算可以轻松解出这个问题。

![format_png 13][]

![format_png 14][]

**如何解决八皇后问题？**

所谓递归回溯，本质上是一种枚举法。这种方法从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后......

如果某一层看遍了所有格子，都无法成功摆放，则回溯到上一个皇后，让上一个皇后右移一格，再进行递归。如果八个皇后都摆放完毕且符合规则，那么就得到了其中一种正确的解法。

说起来有些抽象，我们来看一看递归回溯的详细过程。

1.**第一层**递归，尝试在**第一行**摆放**第一个皇后**：

![format_png 15][]

2.**第二层**递归，尝试在**第二行**摆放**第二个皇后**（前两格被第一个皇后封锁，只能落在第三格）：

![format_png 16][]

3.**第三层**递归，尝试在**第三行**摆放**第三个皇后**（前四格被第一第二个皇后封锁，只能落在第五格）：

![format_png 17][]

4.**第四层**递归，尝试在**第四行**摆放**第四个皇后**（第一格被第二个皇后封锁，只能落在第二格）：

![format_png 18][]

5.**第五层**递归，尝试在**第五行**摆放**第五个皇后**（前三格被前面的皇后封锁，只能落在第四格）：

![format_png 19][]

6.由于所有格子都“绿了”，第六行已经没办法摆放皇后，于是进行回溯，重新摆放**第五个皇后**到**第八格**。：

![format_png 20][]

7.第六行仍然没有办法摆放皇后，第五行也已经尝试遍了，于是回溯到**第四行**，重新摆放**第四个皇后**到**第七格**。：

![format_png 21][]

8.继续摆放第五个皇后，以此类推......

![format_png 22][]

![format_png 23][]

**八皇后问题的代码实现？**

解决八皇后问题，可以分为两个层面：

1.**找出第一种正确摆放方式**，也就是深度优先遍历。

2.**找出全部的正确摆放方式**，也就是广度优先遍历。

由于篇幅优先，我们本篇只介绍如何找出第一种正确摆放方式。

在研究代码实现的时候，我们需要解决几个问题：

**1.国际象棋的棋盘如何表示？**

很简单，用一个长度是8的二维数组来表示即可。

![format_png 24][]

由于这里使用的是int数组，int的初始值是0，代表没有落子。当有皇后放置的时候，对应的元素值改为1。

在这里，二维数组的第一个维度代表横坐标，第二个维度代表纵坐标，并且从0开始。比如chessBoard\[3\]\[4\]代表的是棋盘第四行第五列格子的状态。

**2.如何判断皇后的落点是否合规？**

定义一个check方法，传入新皇后的落点，通过纵向和斜向是否存在其他皇后来判断是否合规。

![format_png 25][]

**3.如何进行递归回溯？**

递归回溯是本算法的核心，代码逻辑有些复杂

![format_png 26][]

**4.如何输出结果？**

这个问题很简单，直接遍历二维数组并输出就可以。

![format_png 27][]

**5.如何把这些方法串起来？**

在main函数里分三步来调用：

第一步：初始化

第二步：递归摆放皇后

第三步：最后输出结果。

其中Queen8是整个类的名字。

![format_png 28][]

最终输出如下：

10000000

00001000

00000001

00000100

00100000

00000010

01000000

00010000

![format_png 29][]

![format_png 30][]

**几点补充：**

1.由于篇幅原因，这一篇只讲了如何找出第一种正确的八皇后摆放。大家如果有兴趣，可以对文中的代码稍作改动，实现找出所有八皇后摆放的代码。

2.**本漫画纯属娱乐，还请大家尽量珍惜当下的工作，切勿模仿小灰的行为哦。**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYkFDSU40TWFYaWNoanVKamV5MVkyazJtV0ZRc2ZRVkVObEtOVDdSSkFLNHZUZHJ0cjVtbnJMQlEvNjQw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYlRiQ3RHTjcxTkllaWJmSExjWjVnUnl1YlpSQnY4aWFBQTFCTzFFVDRuaWNUaGRtZ3dpY2VqU2NyNlEvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYndoRWtNTWJHOVZlYWE1dHRsTFpONklGcUhobjdCZ1A0eloxNUc2Z2pTNXZNemVJNDFBVzVqQS82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYmFLMDE3aWJQdkprUnAzbTc4WUp3V29mSTRxb0NocGdBSVk3c2RwQ2N4NzhndVZ3aHhyUVZrSWcvNjQw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYnNrQm40d3BXSWdBUkFpYk50Z2lhRTNieWZGdHdJaWJXMlp2WWVOUUg5Vmc3ZzIwSDRFaWJpY1ZMdHpRLzY0MA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYlFWMlRJSkRIODk3aWJVN0JiaGtmektCSFFQVUZtVTBpYnpKTVgzZzNJTDN2QUp5YW5kUTFiVG1BLzY0MA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYk9adW80U3d3SGhXclo4T0RpYVBVVWVIaWJYeWN2aHRZRGljSklRMnNYSGU2S3JBTk1BbU1FcnhVQS82NDA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYnVjWGZUU0dldlp3elJpYXlyRE9HZjZpYk9SdFZnTjlvNHBlWjgzb3JYaWNXaGJpYzJtdThtaWE2bVNRLzY0MA?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYmw2Wm1naWNWY1FPa3diV2hpYzFNMTNkVGE2aWNMSTlGd2t5YnVsRTdvUEZndGtnVEE5eVROWUpGZy82NDA?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3FGb3hNTUtNRjk5dUQ4VWdUOXdmcExEWllpYkI2ZWtONXhMWU8zdWliTmozY3J4Z05YNmo2Mk5WRE1KalFjaWN2WlJLTVo0dVNJNlkwemcvNjQw?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3FGb3hNTUtNRjk5dUQ4VWdUOXdmcEx5aDhwMHhDeWNjWkR1ancxdllscEh1VEpmbkVlcnZsb0xWNmp6a25JRWhpYVdMVU5GZzFiaE1RLzY0MA?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYnFVS0tpY3RwR1ZuelZpYXdZMlBiVDJFZlZBNDc5akVGZENhVUxmekU5SGF6YTc2aFEzTk04M3VRLzY0MA?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYm5EMFdSY3B5UlhlWFUxOHkzcXkyWjUza0FPS2tmMGljaWFpY0p3S2lhdldtUjFYWEExWUxsb1VqV1EvNjQw?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYnNBbzBzZUptaWNub0R3QUQ2UmRwc1YweVZ0WnVQMmZxZEpDZGlhNU4xVkE5ZG1uS1BHVXNvNFhBLzY0MA?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYmFnQUlPeTFnS2paRmpQWm5MS3JpY0d0NnpZM2YybnZjOUt1SFg3T3dDQnZwTTVUM0RENWR3aWF3LzY0MA?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYm9NbnZTVngwVWlhWGxDdm1aVEZNUmVtMjFzTk5VS28xWWszdnRCYno2ZTFKMUlpY3lpY3BFR2QzQS82NDA?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYnN3aWMyS2pJVWZnbkFrOE5QTEZSaWNlU0NNWHViY050TThzTjVOVUJkM2lhY3UxbURKak9BUDNxUS82NDA?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYkljVDFENDlweGJrWVZBdDdxaWF6Mkx5ZTR6T2Zhdnk3V1dpYmx2RVZUdHBqYkc4ZFNpYlFFTTA3QS82NDA?x-oss-process=image/format,png
[format_png 18]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYnNvaWF5RngxQzRhU01CWFZNaWFxMlc0TDhHRGU0aWJCd1dlUGljamlhYXJkeUUzNDBtVEUzNU1ONHBnLzY0MA?x-oss-process=image/format,png
[format_png 19]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYlBoaWJZdHE5VUJ2TVY1S3pDS2xQVTdnbm5pYU85QnZESjFiMUxTRDRBT2UxV2FIdXJ3OGVWRmtRLzY0MA?x-oss-process=image/format,png
[format_png 20]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYlE4WnYyOGtMWE9aaWM3YUtKbDdmd2ZMdU0zdDQwS2lhMFlrbVhBaWI5M3pCSUhoaWFjaFNzSDNJaWJRLzY0MA?x-oss-process=image/format,png
[format_png 21]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYmljVGliUTkyWVoyak1pY2Q3QmNlUmJnMkVQRXBlU2pNSlBtcU0yZEFCaEU5eG5NdmhyTDQ5cXNzZy82NDA?x-oss-process=image/format,png
[format_png 22]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYk1Ubk96S2lhYnlpYWFqNzlraExQRTRRcno1NFJZQ2xHWUxRNURGY0c3bk9STmdaVlJBdmxXSmtRLzY0MA?x-oss-process=image/format,png
[format_png 23]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYkNMcEEwWGliTTVKdG10V3VHSDFNNHNKYkdwTEhnWTBiNGNWQTdwMDdJNkVUdERlaDFxT0o5NGcvNjQw?x-oss-process=image/format,png
[format_png 24]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYlJHZVBISjlOMFJpY0I4NXdpY0JhYmlhNW1MOXZLTUZpYTNpY0w5QWxQODRtZ21iV241WkhNSEFqNGlidy82NDA?x-oss-process=image/format,png
[format_png 25]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYk94eXFiZTdNSlNaVjUzSTFYQVlRYUZvU3psbVZGZWdMenNFb3c3aWJMVVQ5SHlBZ3c0eUpLUXcvNjQw?x-oss-process=image/format,png
[format_png 26]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYlpnY2h3MGZvTmhkZ3hOdFc4WDU4V2lhRzVoVVd1TFFZRmlhbDdwOThvVVo1Q3pneTRhYnBzVlJRLzY0MA?x-oss-process=image/format,png
[format_png 27]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYnRnR0hVdTBGWVNudjBpYXBiODRBUnU1U2RHcGhjTnBpYXkzSDFzVjZGZ1dLRlFmc2pCQ3NmMGF3LzY0MA?x-oss-process=image/format,png
[format_png 28]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYndmemVuODJ3SzVXMXdTZ01yY2VDYVh1bkFuR0ZubXVuYndoWWZ6aWI5RzEzZEw1djhLVGJqeWcvNjQw?x-oss-process=image/format,png
[format_png 29]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYlhpY3hZWGliVENaWlk4cGt2WUV2dURCSUpYRENSWTRVT2JRNnFpYkE0cEh5QmNvaWNKc1pydXdOVkEvNjQw?x-oss-process=image/format,png
[format_png 30]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29FRWJ5S2licmtQekRRZW5QenhPWnlpYlpqT2tMNFJXdXBBbmQ1d3lhSjJSTEYwWG1tSGJHSlVCM25YUUpQVkRVUW51YVlXMnZxZHVvZy82NDA?x-oss-process=image/format,png