A team of physicists has created what they claim is the world’s most difficult maze, using a model from the game of chess to create the structure. To the untrained eye, the maze looks like the most intricate snowflake. But for the puzzle lovers among us, it probably seems like a challenge.
The maze is constructed from a Hamiltonian cycle, a graph cycle that visits each node in the graph only once. The same movement pattern appears in the “Knight’s Tour” in chess, whereby a chess piece can visit each space on the board once without repeating before returning to its starting tile.
The team maze works similarly; is a collection of Hamiltonian cycles in quasicrystals. Don’t worry, we’ll explain. A detailed explanation of the construction of the maze was accepted for publication in Physical Review X.
“When we looked at the line shapes we constructed, we noticed that they formed incredibly complex mazes,” Felix Flicker, a physicist at the University of Bristol and co-author of the paper, said in a university publication. “The sizes of the later mazes grow exponentially – and there are an infinite number of them.”
Quasicrystals are a rare type of matter. Ordinary crystals have periodic structures, meaning that their building blocks repeat regularly. But the building blocks of the quasicrystal do not repeat regularly; they have asymmetrical, non-repeating structures, making them bewildering 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 into its constituent atoms with a laser—in other words, one quasicrystal at a time. An example of a 3D quasicrystal is the icosahedron, a 20-sided shape similar in appearance 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 of symmetry… All those 200-year-old rules go out the window – any symmetry is allowed, including the most famous symmetry forbidden for solids, which is an icosahedron. With quasicrystals, suddenly, an infinity of possibilities is available to you.”
Quasicrystals in nature form under rare circumstances. Some were found in lonsdaleite, a mineral that is harder than diamonds and does not occur naturally on Earth but has come down to us in meteorites. In 2021, physicists discovered that quasicrystals formed in trinitite, the strange material that formed after the Trinity bomb test in 1945, which turned swathes of the New Mexican desert into glass.
The latter team presented an algorithm for constructing graphical Hamiltonian cycles on top of two-dimensional spaces called Ammann-Beenker tiles. The team says these two-dimensional labyrinths show Hamiltonian cycles that mimic the atomic patterns of a quasicrystal.
“We show that some quasicrystals provide a special case in which the problem is unexpectedly simple,” Flicker said. “In this environment, we make some seemingly impossible problems solvable. This may include practical purposes that span different fields of science.”
Indeed, there are scientific implications for the model. As noted in the university’s publication, the Hamiltonian cycle provides the fastest way for microscopic imagers, such as scanning tunneling microscopes, to image an object. It also has implications for the use of the quasicrystal in several physics problems, including one that can be used to model protein folding.
But if you’re not involved in any of those fields, you can step back and appreciate the way math reveals some of the most exotic patterns in our physical universe.