Cartoon: what is the eight queens problem?

————— 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—————