漫画：什么是八皇后问题？
————— 第二天 —————
题目是什么意思呢？
国际象棋中的皇后，可以横向、纵向、斜向移动。如何在一个8X8的棋盘上放置8个皇后，使得任意两个皇后都不在同一条横线、竖线、斜线方向上？
让我们来举个栗子，下图的绿色格子是一个皇后在棋盘上的“封锁范围”，其他皇后不得放置在这些格子：
下图的绿色格子是两个皇后在棋盘上的“封锁范围”，其他皇后不得放置在这些格子：
那么，如何遵循规则，同时放置这8个皇后呢？让我们来看看小灰的回答。
————————————
什么是八皇后问题？
八皇后问题是一个古老的问题，于1848年由一位国际象棋棋手提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，如何求解？
以高斯为代表的许多数学家先后研究过这个问题。后来，当计算机问世，通过计算机程序的运算可以轻松解出这个问题。
如何解决八皇后问题？
所谓递归回溯，本质上是一种枚举法。这种方法从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后......
如果某一层看遍了所有格子，都无法成功摆放，则回溯到上一个皇后，让上一个皇后右移一格，再进行递归。如果八个皇后都摆放完毕且符合规则，那么就得到了其中一种正确的解法。
说起来有些抽象，我们来看一看递归回溯的详细过程。
1.第一层递归，尝试在第一行摆放第一个皇后：
2.第二层递归，尝试在第二行摆放第二个皇后（前两格被第一个皇后封锁，只能落在第三格）：
3.第三层递归，尝试在第三行摆放第三个皇后（前四格被第一第二个皇后封锁，只能落在第五格）：
4.第四层递归，尝试在第四行摆放第四个皇后（第一格被第二个皇后封锁，只能落在第二格）：
5.第五层递归，尝试在第五行摆放第五个皇后（前三格被前面的皇后封锁，只能落在第四格）：
6.由于所有格子都“绿了”，第六行已经没办法摆放皇后，于是进行回溯，重新摆放第五个皇后到第八格。：
7.第六行仍然没有办法摆放皇后，第五行也已经尝试遍了，于是回溯到第四行，重新摆放第四个皇后到第七格。：
8.继续摆放第五个皇后，以此类推......
八皇后问题的代码实现？
解决八皇后问题，可以分为两个层面：
1.找出第一种正确摆放方式，也就是深度优先遍历。
2.找出全部的正确摆放方式，也就是广度优先遍历。
由于篇幅优先，我们本篇只介绍如何找出第一种正确摆放方式。
在研究代码实现的时候，我们需要解决几个问题：
1.国际象棋的棋盘如何表示？
很简单，用一个长度是8的二维数组来表示即可。
由于这里使用的是int数组，int的初始值是0，代表没有落子。当有皇后放置的时候，对应的元素值改为1。
在这里，二维数组的第一个维度代表横坐标，第二个维度代表纵坐标，并且从0开始。比如chessBoard[3][4]代表的是棋盘第四行第五列格子的状态。
2.如何判断皇后的落点是否合规？
定义一个check方法，传入新皇后的落点，通过纵向和斜向是否存在其他皇后来判断是否合规。
3.如何进行递归回溯？
递归回溯是本算法的核心，代码逻辑有些复杂
4.如何输出结果？
这个问题很简单，直接遍历二维数组并输出就可以。
5.如何把这些方法串起来？
在main函数里分三步来调用：
第一步：初始化
第二步：递归摆放皇后
第三步：最后输出结果。
其中Queen8是整个类的名字。
最终输出如下：
几点补充：
1.由于篇幅原因，这一篇只讲了如何找出第一种正确的八皇后摆放。大家如果有兴趣，可以对文中的代码稍作改动，实现找出所有八皇后摆放的代码。
2.本漫画纯属娱乐，还请大家尽量珍惜当下的工作，切勿模仿小灰的行为哦。
—————END—————
系列文章：
《漫画：什么是一致性哈希？》
《漫画：什么是B+树？》
《漫画：什么是B-树？》
《漫画：什么是跳跃表？》
《漫画：什么是动态规划？》
《漫画：当程序猿遇上智力测试题》
《漫画：判断 2 的乘方》
《漫画算法：最小栈的实现》
《漫画：什么是大数据？》
《漫画算法：无序数组排序后的最大相邻差值》
《漫画：什么是Bitmap算法？》
《漫画：Bitmap算法 进阶篇》
《什么是A*寻路算法？》
《漫画：当程序员遇上智力题（第四季）》
《漫画：什么是Base64算法？》
《漫画：什么是MD5算法？》
《漫画：如何破解MD5算法？》
《漫画：什么是SHA系列算法？》
《漫画：什么是AES算法？》
《漫画：AES算法的底层原理》
《漫画：什么是红黑树？》
《漫画：什么是HashMap？》
《漫画：高并发下的HashMap》
《漫画：什么是单例模式？（整合版）》
《漫画：什么是架构师》
《漫画：什么是大数据？》
《漫画：什么是微服务？》
《漫画： 什么是人工智能？》
《漫画：什么是数据仓库？》
●本文编号589，以后想阅读这篇文章直接输入589即可
●输入m获取文章目录
推荐↓↓↓
大数据与人工智能
更多推荐《18个技术类微信公众号》
涵盖：程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。
- 发表于:
- 原文链接：http://kuaibao.qq.com/s/20180226B0A57P00?refer=cp_1026
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
