Physicists have created the world’s most difficult maze: ScienceAlert

Daedalus could have learned a thing or two from a team of physicists in the UK and Switzerland.

Taking principles from fractal geometry and the strategic game of chess, they have created what they say is the most difficult maze ever created.

Led by physicist Felix Flicker of the University of Bristol in the United Kingdom, the group has created pathways called Hamiltonian cycles in patterns known as Ammann-Beenker tiles, producing complex fractal mazes that, they say, describe an exotic form of matter. known as quasicrystals.

And it was all inspired by the movement of a knight around a chessboard.

“When we looked at the line shapes we built, we noticed that they formed incredibly complicated mazes. The sizes of subsequent mazes grow exponentially—and there are an infinite number of them,” explains Flicker.

“In a knight’s turn, the chess piece (which jumps two squares forward and one to the right) visits each square of the chessboard only once before returning to its starting square. This is an example of a ‘ Hamiltonian cycle’ – a loop through a map that visits all stopping points only once.”

Open tournament of a knight on a chessboard
An example of a knight’s open tour on a chessboard, with visited squares shaded. For the turn to be ‘closed’, the Knight must end in a square one Knight move from where it started (so it can return to the starting square and go around the board again). (Ilmari Karonen/CC0/Wikimedia Commons)

Quasicrystals are a form of matter that is only very rarely found in nature. They are a kind of strange hybrid of ordered and disordered crystals in solids.

In an ordered crystal—salt, or diamonds, or quartz—the atoms are arranged in a very regular pattern that repeats itself in three dimensions. You can take one part of this grid and overlay it on top of another, and they will match perfectly.

A disordered, or amorphous, solid is one in which the atoms are just all higgledy-piggledy. These include glass and some forms of ice not normally found on Earth.

A maze created by finding a Hamiltonian cycle in an Ammann-Beenker tiling. Do not worry. They can get much, much bigger and harder. A solution can be seen below. (University of Bristol)

A quasicrystal is a material in which the atoms form a pattern, but the pattern does not repeat itself perfectly. It may look quite similar, but the overlapping sections of the pattern will not match.

These similar-looking but not identical patterns are very similar to a mathematical concept called aperiodic plates, which involve patterns of shapes that do not repeat identically.

The famous Penrose plate is one of these. The Ammann-Beenker tile is another.

Using a set of two-dimensional Ammann-Beenker plates, Flicker and his colleagues, physicists Shobhna Singh of Cardiff University in the UK and Jerome Lloyd of the University of Geneva in Switzerland, generated Hamiltonian cycles that they say describe the atomic model of a quasicrystal. .

An Ammann-Beenker tiling with a thicker black line tracing the Hamiltonian path visiting each vertex. The purple lines are not part of the tiles. (Singh et al., Phys. Rev. X2024)

The cycles they create visit each atom in the quasicrystal only once, connecting all the atoms in a single line that never crosses itself but continues cleanly from start to finish. And this can scale infinitely, generating a kind of mathematical pattern known as a fractal, in which the smallest parts resemble the largest.

This line then naturally produces a maze, with a starting point and an exit. But the research has much larger implications beyond entertaining ant children at dinner parties.

For one, finding Hamiltonian cycles is notoriously difficult. A solution that would allow the identification of Hamiltonians has the potential to solve many other complex mathematical problems, from complex path-finding systems to protein folding.

And, interestingly, it has implications for carbon capture through adsorption, an industrial process that involves collecting molecules in a liquid by attaching them to crystals. If we could use quasicrystals for this process instead, the flexible molecules could be packed more tightly by stretching along the Hamiltonian cycle there.

A possible solution to the above maze. (University of Bristol)

“Our work also shows that quasicrystals can be better than crystals for some adsorption applications,” says Singh.

“For example, bent molecules will find more ways to land on the irregularly arranged atoms of quasicrystals. Quasicrystals are also brittle, meaning they break easily into small grains. This maximizes their surface area for absorption.”

And if you happen to have a minotaur you need to store somewhere, we think we know someone who can help.

The research was published in Physical Review X.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top