A team of physicists have created what they claim is the most difficult maze ever created, using a chess pattern to create its structure. To the untrained eye, the maze looks like the most complicated snowflake. But for the puzzle enthusiasts among us, it probably looks like a challenge.
The maze is constructed from a Hamiltonian cycle, a graph cycle that visits each node on the graph only once. The same pattern of movement can be seen in the “Knight’s tour” in chess, where the chess piece can visit each space on the board once without repeating itself before returning to its starting tile.
The team’s maze works in a similar way; it’s an assembly of Hamiltonian cycles in quasicrystals. Don’t worry, we’ll explain. A detailed explanation of the maze’s construction was accepted for publication in Physical assessment X.
“When we looked at the shapes of the lines we constructed, we noticed that they formed incredibly complicated mazes,” Felix Flicker, a physicist at the University of Bristol and co-author of the paper, said in a university press release. “The size of the subsequent mazes grows exponentially – and there are infinitely many of them.”
Quasicrystals are a rare type of matter. Regular crystals have periodic structures, meaning their building blocks repeat regularly. But the building blocks of quasicrystals don’t repeat regularly; they have asymmetric, non-repeating structures, making them confusing in three dimensions and almost magical in others; in 2022, a team of physicists managed to keep a quantum system coherent for longer by directing a quasicrystalline pattern onto its constituent atoms with lasers—in other words, a quasicrystal in time. An example of a 3D quasicrystal is the icosahedron, a 20-sided shape that resembles a standard soccer ball in appearance. As one physicist told Gizmodo in 2021:
“The moment you go from periodic to quasi-periodic, all bets on the symmetry of the orbit are off… All those 200-year-old rules go out the window — any symmetry is allowed, including the most famous forbidden symmetry for solids, which is the symmetry of an icosahedron. With quasicrystals, you suddenly have an infinite number of possibilities at your disposal.”
Quasicrystals in nature form under rare conditions. Some have been found in lonsdaleite, a mineral harder than diamonds that does not occur naturally on Earth but has come down to us in meteorites. In 2021, physicists discovered that quasicrystals formed in trinitite, the bizarre material that formed after the 1945 Trinity bomb test, which turned parts of the New Mexico desert into glass.
The recent team introduced an algorithm for building Hamiltonian graph cycles on two-dimensional spaces, called Ammann-Beenker tilings. The team says that these two-dimensional mazes show Hamiltonian cycles that mimic the atomic patterns of a quasicrystal.
“We show that certain quasicrystals provide a special case in which the problem is unexpectedly easy,” Flicker said. “In this setting, we therefore make a number of seemingly impossible problems tractable. This can include practical purposes that span several areas of science.”
There are indeed scientific implications for the pattern. As noted in the university release, the Hamiltonian cycle provides the fastest way for microscopic imagers, such as scanning tunneling microscopes, to cover an object. There are also implications for using the quasicrystal in various physics problems, including one that could be used to model protein folding.
But if you don’t work in one of those fields, you can take a step back and admire how mathematics reveals some of the most exotic patterns in our physical universe.