当前位置:网站首页>Cartoon: what is the eight queens problem?
Cartoon: what is the eight queens problem?
2022-07-05 16:09:00 【Small ash】
————— the second day —————
What does the title mean ?
The queen of chess , Can be horizontal 、 The longitudinal 、 Moving obliquely . How to 8X8 On the chessboard 8 A queen , bring Neither queen is on the same line 、 A vertical bar 、 In the diagonal direction ?
Let's raise a chestnut , The green grid below is a queen on the chessboard “ Blockade area ”, Other queens are not allowed to be placed in these boxes :
The green grid below shows two queens on the chessboard “ Blockade area ”, Other queens are not allowed to be placed in these boxes :
that , How to follow the rules , At the same time, place this 8 A queen ? Let's take a look at Xiao Hui's answer .
————————————
What is the question of eight queens ?
The eight queens problem is an old one , On 1848 It was proposed by a chess player : stay 8×8 GE's chess set eight queens , Make it impossible to attack each other , That is, no two Queens can be in the same line 、 On the same column or slash , How to solve ?
Many mathematicians represented by Gauss have studied this problem one after another . later , When computers came out , This problem can be easily solved by the operation of computer program .
How to solve the eight queens problem ?
So called recursive backtracking , It's essentially an enumeration . This method starts from the first line of the chessboard and tries to place the first queen , After placing it successfully , Recursive one layer , Then follow the rules to place the second queen on the second line of the chessboard . If the current position cannot be placed , Move one space to the right and try again , If it's placed successfully , Then continue to recurse one layer , Put the third queen ......
If one layer looks through all the squares , Can't be placed successfully , Back to the last queen , Let the last queen move one space to the right , And then recursion . If all eight queens are in place and conform to the rules , Then we get one of the correct solutions .
It's a little abstract , Let's take a look at the detailed process of recursive backtracking .
1. first floor recursive , Try to first line put The first queen :
2. The second floor recursive , Try to The second line put The second queen ( The first two spaces are blocked by the first queen , It's in the third frame ):
3. The third level recursive , Try to The third line put The third queen ( The first four spaces are blocked by the first and second queens , It's only the fifth ):
4. The fourth level recursive , Try to In the fourth row put The fourth queen ( The first block is blocked by the second queen , It's in the second frame ):
5. The fifth floor recursive , Try to The fifth row put The fifth queen ( The first three spaces are blocked by the queen in front , Only in the fourth ):
6. Because all grids are “ It's green ”, There's no way to put the queen in the sixth line , So we go back , Rearrange The fifth queen To The eighth grid .:
7. The sixth line still has no way to put the queen , The fifth line has been tried all over , So back to In the fourth row , Rearrange The fourth queen To Seventh case .:
8. Keep putting the fifth queen , And so on ......
Eight queens problem code implementation ?
Solve the problem of eight queens , It can be divided into two levels :
1. Find the first way to put it right , That's depth first traversal .
2. Find the right way to put it all , That's breadth first traversal .
Because space takes precedence , We'll just talk about how to find out the first way to put it right .
When studying code implementation , We need to solve a few problems :
1. How does the chess board represent ?
It's simple , Using a length is 8 Can be represented by a two-dimensional array of .
Because it's used here int Array ,int The initial value of 0, It means there's no end . When there is a queen , The corresponding element value is changed to 1.
ad locum , The first dimension of a two-dimensional array represents the abscissa , The second dimension represents the ordinate , And from 0 Start . such as chessBoard[3][4] Represents the state of the fourth row and fifth column of the chessboard .
2. How to judge whether the Queen's landing site is compliant ?
Define a check Method , Introduce the landing point of the new queen , Compliance is judged by the presence of other queens in the vertical and oblique directions .
3. How to do recursive backtracking ?
Recursive backtracking is the core of this algorithm , The logic of the code is a bit complicated
4. How to output results ?
The question is simple , Directly traverse the two-dimensional array and output it .
5. How to string these methods together ?
stay main Function is called in three steps :
First step : initialization
The second step : The queen of recursion
The third step : Final output .
among Queen8 It's the name of the whole class .
The final output is as follows :
10000000
00001000
00000001
00000100
00100000
00000010
01000000
00010000
Some supplements :
1. For reasons of length , This article only talks about how to find out the first correct eight queens . If you are interested in , You can make some changes to the code in this article , Implementation to find out all the eight queens put the code .
2. This cartoon is purely entertainment , Please cherish your current work as much as possible , Don't imitate Xiao Hui's behavior .
—————END—————
边栏推荐
- Boost the development of digital economy and consolidate the base of digital talents - the digital talent competition was successfully held in Kunming
- vant popup+其他组件的组合使用,及避坑指南
- Which keywords will conflict with the abstract keyword
- 写单元测试的时候犯的错
- 单商户 V4.4,初心未变,实力依旧!
- Maximum common subsequence
- 21.[STM32]I2C协议弄不懂,深挖时序图带你编写底层驱动
- 18.[STM32]读取DS18B20温度传感器的ROM并实现多点测量温度
- [graduation season] as a sophomore majoring in planning, I have something to say
- Use of set tag in SQL
猜你喜欢
开发中Boolean类型使用遇到的坑
Appium automation test foundation - appium basic operation API (I)
Verilog realizes the calculation of the maximum common divisor and the minimum common multiple
通过的英特尔Evo 3.0整机认证到底有多难?忆联科技告诉你
18.[stm32] read the ROM of DS18B20 temperature sensor and realize multi-point temperature measurement
obj集合转为实体集合
六种常用事务解决方案,你方唱罢,我登场(没有最好只有更好)
ES6深入—ES6 Class 类
Replknet: it's not that large convolution is bad, but that convolution is not large enough. 31x31 convolution. Let's have a look at | CVPR 2022
Codasip为RISC-V处理器系列增加Veridify安全启动功能
随机推荐
我们为什么要学习数学建模?
【毕业季】作为一名大二计科在校生,我有话想说
Is it safe for Guotai Junan to open an account online
修改pyunit_time使得其支持‘xx~xx月’的时间文本
obj集合转为实体集合
程序员如何提升自己的格局?
SQL injection sqllabs (basic challenges) 1-10
降本40%!Redis多租户集群的容器化实践
单商户 V4.4,初心未变,实力依旧!
Boost the development of digital economy and consolidate the base of digital talents - the digital talent competition was successfully held in Kunming
Appium automation test foundation - appium basic operation API (II)
Interval DP (gravel consolidation)
RLock锁的使用
10分钟帮你搞定Zabbix监控平台告警推送到钉钉群
Five common negotiation strategies of consulting companies and how to safeguard their own interests
The list set is summed up according to a certain attribute of the object, the maximum value, etc
ES6 drill down - Async functions and symbol types
List uses stream flow to add according to the number of certain attributes of the element
五种常见的咨询公司谈判策略以及如何维护自己的利益
ES6 drill down - ES6 generator function