漫画:什么是八皇后问题?

点击上方“程序员小灰”,选择“置顶公众号”

有趣有内涵的文章第一时间送达!



漫画:什么是八皇后问题?



漫画:什么是八皇后问题?



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



漫画:什么是八皇后问题?



漫画:什么是八皇后问题?



漫画:什么是八皇后问题?



题目是什么意思呢?


国际象棋中的皇后,可以横向、纵向、斜向移动。如何在一个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是整个类的名字。


漫画:什么是八皇后问题?


最终输出如下:


10000000

00001000

00000001

00000100

00100000

00000010

01000000

00010000



漫画:什么是八皇后问题?



漫画:什么是八皇后问题?



几点补充:


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


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




—————END—————


漫画:什么是八皇后问题?



喜欢本文的朋友们,欢迎长按下图关注订阅号程序员小灰,收看更多精彩内容

漫画:什么是八皇后问题?


原文始发于微信公众号(程序员小灰):漫画:什么是八皇后问题?

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 漫画:什么是八皇后问题?

我还会在以下平台发布内容

GitHub 哔哩哔哩