Unsolvable puzzle for 36 officers
Can you solve the puzzle?
Suppose you command an army of 6 legions, each with 6 officers of different ranks. So can you line these 36 officers into a square of 6×6 so that there are no duplicate corps or duplicate ranks in each row or column?
This is a puzzle proposed by Leonhard Euler in 1779. When visualizing this puzzle, we can distinguish the legions by the colors green, purple, red, orange, blue, and yellow, and then borrow the king, queen, car, elephant, horse, and soldier in chess to describe 6 different ranks.
The puzzles involving 36 officers from 6 legions can be represented by chess with different colors, which represent different legions, and the king, queen, car, elephant, horse, and soldier in chess represent different ranks.
Like all puzzle lovers, Euler herself tried to think about the problem, but without success. In 1782, Euler wrote: "After painstakingly solving, although it is impossible to give a rigorous proof, it is impossible to admit that this arrangement (placing 36 officers in this form in the square of 6×6) is impossible." ”
At the time, Euler proved that for this puzzle, any number of legions and ranks that do not exist in the form of 4k+2 exists. He stated that the method of proof he had adopted was not suitable for proof of such a form of figure.
More than a century later, the French mathematician Gaston Tarry proved in 1901 that Euler's 36 officer puzzles could indeed not be arranged in a square of 6×6 in a manner that was not repeated by rank and legion. However, when both ranks and legions are changed to 5, or both to 7, the puzzle can be easily solved.
5×5 squares can be filled with 5 different levels and 5 different colored pieces, and there are no duplicate levels or colors in the same row or column.
By 1960, mathematicians had used computers to prove that the puzzle had a solution to any number of legions and ranks greater than 2, except for 6.
Latin phalanx: classical vs quantum
The 36 officer puzzles may remind you of many puzzle games made up of rows and columns in a square, such as Sudoku. In fact, Sudoku is a Kind of Latin Phalanx. The so-called Latin square is a square matrix of symbols (numbers and letters), in which each symbol appears only once in each row and column. If you combine two Latin squares with the same size but different symbols, you get a Greek Latin square, also known as euler square, which contains pairs of symbols.
Two Latin squares are combined to get a Greek Latin square.
As Euler realized, if there were a solution to the 36 officers' puzzle, it would be a 6x6 Greek Latin phalanx. It contains two sets of attributes, rank and legion, and both attributes are required to satisfy the rules of the Latin phalanx. While Euler believes that such a 6×6 Greek-Latin phalanx does not exist, the situation seems to have changed recently.
In a paper recently submitted to Physical Review Letters, a group of quantum physicists from India and Poland said they quantized the puzzle using quantum mechanics ideas, successfully putting Euler's 36 officers into one such 6×6 squares.
If every lattice entry in a Latin square is quantum, it will have an unusual set of properties. Because in quantum mechanics, particles like electrons can be in "superposition states" in a variety of possible states. Mathematically, quantum states can be represented by vectors with length and direction, while superposition is an arrow formed by combining multiple vectors.
In the classic Latin phalanx, the symbols on each row and each column are not repeatable. In contrast to classical Latin squares, the quantum states on each row or column of a quantum Latin square must correspond to vectors perpendicular to each other.
The Quantum Edition puzzle proves Euler "wrong"
For the 36 Officer Puzzle, in the classic version, each entry in the phalanx represents an officer with a clear rank and corps. But in the new study, the quantum version of an officer is made up of the superposition of its ranks and legions. For example, an officer can be a red king and an orange queen superposition.
Crucially, there is an entangled relationship between the quantum states that make up these officers, in other words, there is a correlation between the different entries. If a red king is entangled with an orange queen, then even if the king and queen are in the superposition of multiple legions at the same time, it can be known that the queen is orange when the king is red. Because of this particular entanglement property, officers on each row or column can be perpendicular to each other.
To prove this theory, the researchers needed to construct a phalanx of 6×6 filled by these quantum officers. Since there are a large number of possible combinations as well as entanglements, they must come with the help of the computer. In this phalanx, the researchers first enter an approximate solution to the classic version of the puzzle. In this approximation solution, the arrangement of the 36 classic officers in a row or column has only a small number of ranks and corps repetitions.
They then applied an algorithm to the solution that would adjust this arrangement to a true quantum solution. This algorithm works a bit like solving a Rubik's Cube with brute force - fix the first row first, then fix the first column, fix the second column... As they repeat this algorithm over and over again, they can get closer and closer to the real solution.
Using this algorithm, they ended up with a real solution to the mystery of 36 officers. In a sense, it proves that Euler's judgment of the 36 officers' puzzle is "wrong". But Euler in the 18th century could not have imagined the possibility of a quantum officer. It is worth mentioning that the new solution has a feature, that is, the ranks of officers are only entangled with adjacent ranks, such as king and queen, car and elephant, horse and soldier... The legions were entangled only with the adjacent corps.
It's not just games
This is the latest achievement of the quantum version of the Latin phalanx puzzle. It is worth mentioning that it is proved that this puzzle that began 243 years ago has a quantum solution, not only a puzzle game, but also has practical application significance. For example, this achievement can be applied to the field of quantum communication and quantum computing.
#创作团队:
Author: Sasuke
Typography: Wenwen
#参考来源:
https://www.quantamagazine.org/eulers-243-year-old-impossible-puzzle-gets-a-quantum-solution-20220110/
https://plus.maths.org/content/36-officers-problem
http://www.ams.org/publicoutreach/feature-column/fcarc-latinii1
#图片来源:
Cover image source: PIRO4D/Pixabay
Illustration: MR1313 / Pixabay
Illustration design: Wenwen