当前位置:网站首页>漫画:什么是八皇后问题?
漫画:什么是八皇后问题?
2022-07-05 15:35:00 【小灰】
————— 第二天 —————
题目是什么意思呢?
国际象棋中的皇后,可以横向、纵向、斜向移动。如何在一个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—————
边栏推荐
- [Netease Yunxin] research and practice of super-resolution technology in the field of real-time audio and video
- 我们为什么要学习数学建模?
- Appium automation test foundation - appium basic operation API (I)
- Obj resolves to a set
- 16.[STM32]从原理开始带你了解DS18B20温度传感器-四位数码管显示温度
- 力扣今日题-729. 我的日程安排表 I
- lv_ font_ Conv offline conversion
- Six common transaction solutions, you sing, I come on stage (no best, only better)
- Li Kou today's question -729 My schedule I
- 具有倍数关系的时钟切换
猜你喜欢
verilog实现计算最大公约数和最小公倍数
Data communication foundation OSPF Foundation
RepLKNet:不是大卷积不好,而是卷积不够大,31x31卷积了解一下 | CVPR 2022
研发效能度量指标构成及效能度量方法论
Xiao Sha's arithmetic problem solving Report
项目sql中批量update的时候参数类型设置错误
Data communication foundation smart_ Link_&_ Monitor_ Link
Use of set tag in SQL
ES6深入—async 函数 与 Symbol 类型
【 note 】 résoudre l'erreur de code IDE golang
随机推荐
Basic JSON operations of MySQL 5.7
Reproduce ThinkPHP 2 X Arbitrary Code Execution Vulnerability
sql中set标签的使用
抽象类中子类与父类
This article takes you through the addition, deletion, modification and query of JS processing tree structure data
Parameter type setting error during batch update in project SQL
vant popup+其他组件的组合使用,及避坑指南
list去重并统计个数
18.[STM32]读取DS18B20温度传感器的ROM并实现多点测量温度
21. [STM32] I don't understand the I2C protocol. Dig deep into the sequence diagram to help you write the underlying driver
Mistakes made when writing unit tests
RLock锁的使用
效果编辑器新版上线!3D渲染、加标注、设置动画,这次一个编辑器就够了
【简记】解决IDE golang 代码飘红报错
list集合根据对象某属性求和,最大值等
Arduino controls a tiny hexapod 3D printing robot
Information collection of penetration test
Coding devsecops helps financial enterprises run out of digital acceleration
开发中Boolean类型使用遇到的坑
修改pyunit_time使得其支持‘xx~xx月’的时间文本