————— the next day —————
What do they mean?
A chess queen that can move horizontally, vertically, or diagonally. How do you place 8 queens on an 8X8 board so that no two queens are on the same horizontal, vertical, or diagonal line?
For example, the green squares below are “blocked areas” where a queen can be placed on the board, and no other queen can be placed on these squares:
The green squares below are the “blocked areas” of the two queens on the board, and no other queens can be placed on these squares:
So how do you follow the rules and place all eight queens at once? Let’s take a look at Xiao Grey’s answer.
— — — — — —
What is the eight Queens problem?
The eight Queens problem is an ancient problem, proposed by a chess player in 1848: how to solve an 8×8 chess board with eight queens so that they cannot attack each other, that is, no two queens can be in the same row, column or slash?
Many mathematicians represented by Gauss have studied this problem successively. Later, when computers came along, it was easy to solve the problem with computer programs.
How to solve the eight queens problem?
Recursive backtracking is essentially an enumeration method. This method tries to place the first queen in the first row of the board, and then recurses to the second queen in the second row of the board. If the current position cannot be placed, move one space to the right and try again. If the placement is successful, continue recursing one layer and place the third queen……
If a layer looks at all the squares and fails, go back to the previous queen, move the previous queen one space to the right, and recurse again. If all eight queens are in place and in accordance with the rules, then you have one of the correct solutions.
It’s a little abstract, but let’s look at the details of recursive backtracking.
1. Level 1 recursion, try to place the first queen in the first row:
2. For the second recursion, try to place the second queen in the second row (the first two squares are blocked by the first queen and can only fall in the third square) :
3. Third level recursion, try to place the third queen in the third row (the first four squares are blocked by the first and second queens, and can only fall in the fifth square) :
4. Fourth level recursion, try to place the fourth queen in the fourth row (the first square is blocked by the second queen, can only fall in the second square) :
5. Recursion at the fifth level, try to place the fifth queen in the fifth row (the first three squares are blocked by the queens in front and can only fall in the fourth square) :
6. Since all the squares were “green”, there was no way to put the queen in the sixth row, so I backtracked and rearranged the fifth queen to the eighth grid. :
7. There is still no way to place the queen in the sixth row, and the fifth row has also been tried, so go back to the fourth row and re-place the fourth queen to the seventh grid. :
8. Continue with the fifth queen, and so on……
Eight queen problem code implementation?
The solution to the eight Queens problem can be divided into two aspects:
1. Find the first correct placement, depth first traversal.
2. Find all the right layouts, known as breadth-first traversal.
Because space is a priority, this article will only show you how to find the first correct placement.
When exploring code implementation, we need to address several issues:
1. How is the chess board represented?
It’s easy to write it as a two-dimensional array of length 8.
Since we’re using an int array, the initial value of int is 0, which means there are no children. When a queen is placed, the value of the element is changed to 1.
Here, the first dimension of the two-dimensional array represents the x-coordinate, the second dimension represents the y-coordinate, and starts at 0. For example, chessBoard[3][4] represents the state of the fourth row and fifth column of the board.
2. How to judge whether the queen’s landing point is in compliance?
Define a check method, pass in the new queen’s landing point, by longitudinal and diagonal presence of other queens to determine compliance.
3. How to perform recursive backtracking?
Recursive backtracking is the core of this algorithm, and the code logic is complicated
4. How to output the results?
The problem is simple, just iterate through a two-dimensional array and print it.
How do you string these methods together?
This is called in three steps in main:
Step 1: Initialization
Step 2: Recursively place the queen
Step 3: Output the final result.
Queen8 is the name of the entire class.
The final output is as follows:
10000000
00001000
00000001
00000100
00100000
00000010
01000000
00010000
A few points to add:
1. Due to the lack of space, this chapter only describes how to find the first correct eight queens. If you are interested, you can make a few changes to the code in the article to find the code of all eight queens.
2. This cartoon is purely entertainment, please cherish the present work as much as possible, do not imitate xiao Hui’s behavior.
— — the END — — –
If you like this article, please long click the picture below to follow the subscription number programmer Xiao Grey and watch more exciting content
