preface

The concept is introduced

1. Basic concepts

  • Latin square is an n-by-n square in which there are exactly n different elements, each of which appears only once in the same row or column. (Note: source: Baidu Encyclopedia)

2. Relevant history

  • It is said that Frederick the Great of Prussia formed an honor guard consisting of 36 officers from six armies, each with a colonel, lieutenant colonel, major, captain, lieutenant, and second lieutenant. He wanted the 36 officers to form a six-by-six square, and each row, each column, would have six officers from different units and different ranks. To his annoyance, no matter how hard he racked his brains, he could not arrange them.
  • Later, he went to the famous Swiss mathematician Euler. Euler found this an impossible task.
  • If n by n officers from n units of n ranks can form a square, each row, each column of N officers from different units and ranks, then this square is called an orthogonal Latin square. Euler guessed at

N = 2,6,10,14,18,… , the orthogonal Latin square matrix does not exist.

  • However, in the 1960s, people used computers to build an orthogonal Latin square matrix of n=10, overturning Euler’s guess. It is known that all orthogonal Latin square matrices exist except n=2,6, and there are many ways to construct them.

The principle of interpretation

  • When n=4, the n× N Latin square matrix is shown in the figure below

  • You can see that the numbers 1, 2, 3, and 4 are in each column in each row, and there are no duplicate numbers in each column in any row.
  • Here we will explain in detail the realization principle of 4×4 Latin square matrix
  1. The first time, we put the numbers 1, 2, 3, and 4 in the first row in order

  1. The second time, we circle the numbers 1,2,3,4 one bit to the right to become 2,3,4,1, and then place them in the second row in the order shown below

  1. For the third time we circle the numbers 2,3,4,1 one bit to the right to become 3, 4, 1, and then place them in the third row in the order shown below

  1. For the fourth time, we cycled the numbers 3,4,1,2 to the right one bit to 4,1,2,3, and then placed them in the fourth row in the order shown below

  1. At this point, the realization of the 4×4 Latin square matrix is complete. You are already smart enough to realize that the Latin square matrix is implemented using a single loop linked list.

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