A team of physicists has created a maze that they claim is the most difficult, using a pattern from the game of chess to make the structure. To the untrained eye, the maze looks like the most complicated snowflake. But to the puzzle-lovers 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 just once. The same pattern of movement is on display in the “Knight’s tour” in chess, by which the chess piece can visit every space on the board once without repeating itself before returning to its starting tile.
The team’s maze works similarly; it is an assemblage 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 Review X.
“When we looked at the shapes of the lines we constructed, we noticed they formed incredibly intricate mazes,” said Felix Flicker, a physicist at the University of Bristol and co-author of the paper, in a university release. “The sizes of subsequent mazes grow exponentially – and there are an infinite number of them.”
Quasicrystals are a rare type of matter. Ordinary crystals have periodic structures, meaning their building blocks regularly repeat. But quasicrystal’s building blocks don’t repeat regularly; they have asymmetric, non-repeating structures, making them perplexing in three dimensions and almost magical in others; in 2022, a team of physicists managed to keep a quantum system coherent for longer by blasting a quasicrystalline pattern at the constituent atoms with lasers—in other words, a quasicrystal in time. One example of a 3D quasicrystal is the icosahedron, a 20-sided shape similar in look to a standard soccer ball. As one physicist told Gizmodo in 2021:
“The moment you go from periodic to quasi-periodic, all bets are off on the symmetry…All those 200-year 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, suddenly, an infinitude of possibilities is available to you.”
Quasicrystals in nature form in rare circumstances. Some were found in lonsdaleite, a mineral that’s harder than diamonds and which doesn’t occur naturally on Earth, but has rained down to us in meteorites. In 2021, physicists found that quasicrystals formed in trinitite, the bizarre material that formed in the wake of the Trinity bomb test in 1945, which turned stretches of the New Mexican desert into glass.
The recent team introduced an algorithm for building Hamiltonian graph cycles on top of two-dimensional spaces called Ammann-Beenker tilings. The team says that these two-dimensional mazes show the Hamiltonian cycles mimicking a quasicrystal’s atomic patterns.
“We show that certain quasicrystals provide a special case in which the problem is unexpectedly simple,” Flicker said. “In this setting, we therefore render some seemingly-impossible problems tractable. This could include practical purposes spanning different realms of science.”
Indeed, there are scientific implications for the pattern. As noted in the university release, the Hamiltonian cycle provides the fastest way for microscopic imagers, like scanning tunneling microscopes, to cover an object. There are also implications for using the quasicrystal in several physics problems, including one which can be used for modeling protein folding.
But unless you’re involved in any of those fields, you can step back and appreciate the way mathematics reveals some of the more exotic patterns in our physical universe.
