preface

The concept is introduced

1. The origin of the eight Queens problem

  • The Eight Queens problem, proposed by chess player Max Bethel in 1848, is a typical example of backtracking algorithms.
  • Problem description: eight queens are placed on an 8×8 chess board so that they cannot attack each other, that is, no two queens can be in the same row, column or diagonal diagonal line.
  • How many kinds of pendulum are there?

The principle of interpretation

  • Due to space limitation, we will simplify the eight Queens problem to the four Queens problem to explain its principle (the eight Queens problem and the four Queens problem are the same principle).
  1. Step one, we start with the first row and iterate through all the columns in the first row to find the first suitable position for the queen. The empress position is shown on a black background. The effect is shown below

  1. Because no two queens can be in the same row, column, or diagonal line. So the position on the row, column, and diagonal of the first queen is a dangerous position, and no second queen can be placed. The hazardous locations are shown on a red background, and the safe locations are shown on a green background. The effect is shown below

  1. In the second step, we start with the second row and iterate through all the columns in the second row to find the first suitable position for the queen within the range of safe positions. The empress position is shown on a black background. The effect is shown below

  1. Because no two queens can be in the same row, column, or diagonal line. So the position on the row, column, and diagonal of the second queen is a dangerous position, and no third queen can be placed. The hazardous locations are shown on a red background, and the safe locations are shown on a green background. The effect is shown below

  1. Step 3, we start from the third row, walk through all the columns in the third row, in the safe position range to find the first suitable position for the queen. We can’t find a place for the queen in the third row, so we go back and reposition the second queen. The effect is shown below

  1. Because no two queens can be in the same row, column, or diagonal line. So the position on the row, column, and diagonal of the second queen is a dangerous position, and no third queen can be placed. The hazardous locations are shown on a red background, and the safe locations are shown on a green background. The effect is shown below

  1. Step 4, we start from the third row, traverse all the columns in the third row, find the first suitable position for the queen within the safe position range. The empress position is shown on a black background. The effect is shown below

  1. Because no two queens can be in the same row, column, or diagonal line. So the position on the row, column, and diagonal of the third queen is a dangerous position, and no fourth queen can be placed. The hazardous locations are shown on a red background, and the safe locations are shown on a green background. The effect is shown below

  1. Step 5, we start from the fourth row, walk through all the columns in the fourth row, in the safe position range to find the first suitable position for placing the queen. We can’t find a place for the queen on the fourth line, so we go back. Since there are no alternative positions for the second and third queens, we reposition the position of the first queen. The effect is shown below

  1. Because no two queens can be in the same row, column, or diagonal line. So the position on the row, column, and diagonal of the first queen is a dangerous position, and no second queen can be placed. The hazardous locations are shown on a red background, and the safe locations are shown on a green background. The effect is shown below

  1. In step 6, we start with the second row and iterate through all the columns in the second row to find the first suitable position for the queen within the range of safe positions. The empress position is shown on a black background. The effect is shown below

  1. Because no two queens can be in the same row, column, or diagonal line. So the position on the row, column, and diagonal of the second queen is a dangerous position, and no third queen can be placed. The hazardous locations are shown on a red background, and the safe locations are shown on a green background. The effect is shown below

  1. In step 7, we start with the third row and iterate through all the columns in the third row to find the first suitable position for the queen within the range of safe positions. The empress position is shown on a black background. The effect is shown below

  1. Because no two queens can be in the same row, column, or diagonal line. So the position on the row, column, and diagonal of the third queen is a dangerous position, and no fourth queen can be placed. The hazardous locations are shown on a red background, and the safe locations are shown on a green background. The effect is shown below

  1. In step 8, we start with row 4 and iterate through all the columns in row 4 to find the first suitable position for the queen within the safe position range. The empress position is shown on a black background. The effect is shown below

  1. So far, we have managed to place four queens on a 4×4 chess board so that they cannot attack each other, meaning that no two queens can be on the same row, column, or diagonal line. Of course, that’s just one way to do it, but there’s another way to do it. Leave it to the reader.

Results show

For more algorithm learning, please pay attention to my public number

instructions

  • In the public number to reply to the “algorithm source” to obtain the source code of ten classic algorithms
  • Reply “Algorithm books” in the public account to get the classic introduction algorithm books
  • Reply “data structure” in the public number to obtain data structure related source code