The puzzle in question is Leonhard Euler ’s 36 officers puzzle:
In 1779, the Swiss mathematician Leonhard Euler posed a puzzle that has since become famous: Six army regiments each have six officers of six different ranks. Can the 36 officers be arranged in a 6-by-6 square so that no row or column repeats a rank or regiment?
The puzzle is easily solved when there are five ranks and five regiments, or seven ranks and seven regiments. But after searching in vain for a solution for the case of 36 officers, Euler concluded that “such an arrangement is impossible, though we can’t give a rigorous demonstration of this.” More than a century later, the French mathematician Gaston Tarry proved that, indeed, there was no way to arrange Euler’s 36 officers in a 6-by-6 square without repetition. In 1960, mathematicians used computers to prove that solutions exist for any number of regiments and ranks greater than two, except, curiously, six.
Daniel Garisto, “Euler’s 243-Year-Old ‘Impossible’ Puzzle Gets a Quantum Solution” at Quanta (January 21, 2022)
But now, says Daniel Garisto,
But whereas Euler thought no such 6-by-6 square exists, recently the game has changed. In a paper posted online and submitted to Physical Review Letters, a group of quantum physicists in India and Poland demonstrates that it is possible to arrange 36 officers in a way that fulfills Euler’s criteria — so long as the officers can have a quantum mixture of ranks and regiments. The result is the latest in a line of work developing quantum versions of magic square and Latin square puzzles, which is not just fun and games, but has applications for quantum communication and quantum computing.
Daniel Garisto, “Euler’s 243-Year-Old ‘Impossible’ Puzzle Gets a Quantum Solution” at Quanta (January 21, 2022)
The paper is open access.
Schrodinger’s cat figured it out a long time ago but never got around to telling anyone. 😉
You may also wish to read: How quantum computing can and can’t help us here in Macro World. Quantum computing could easily break down current encryption schemes. Quantum computing can help us create much safer encryption in exchange but currently it requires very cold temperatures in order to work.