Strange crystal structure reveals incredibly complex maze

An algorithm designed to find the most efficient path from atom to atom in a strange kind of crystal turns out to create incredibly complex mazes. In addition to building mazes, the technique could also be useful for speeding up certain industrial chemical reactions.

The crystals in question are called quasicrystals because their atoms are arranged in a repeating fashion like normal crystals, but they exhibit more complex and unpredictable symmetries. Although such crystals have been synthesized in laboratories and were produced during the first nuclear weapon detonation in 1945, only one natural source has been found so far: a meteorite found in Russia in 1985.

“Quasicrystals have all the symmetries that normal crystals don’t have. [normal] The crystals are very interesting.” Felix Flicker Professor at the University of Bristol in the UK. “It’s a very beautiful area of mathematics, but you can appreciate that beauty directly without knowing the details.”

Fricker and his colleagues developed an algorithm to quickly generate paths that contact every atom in a quasicrystal exactly once. Diagrams of these paths form beautiful maze-like structures.

Creating such a pathway is known in computer science as an NP-complete problem, a problem that becomes exponentially more complicated as the number of atoms increases. These problems can quickly become virtually impossible to compute at large scales, but the researchers have found that in some quasicrystals the problem is unexpectedly simple.

“This was quite surprising, since this problem in general is known to be essentially unsolvable and, since these quasicrystals do not have translational symmetry, it did not seem to offer any obvious simplifications,” Fricker says.

Developing such a pathway, Fricker says, could be put to practical use in a laboratory technique called scanning tunneling microscopy, in which an extremely sharp tip is maneuvered over a material to sense individual atoms one by one, building up an atomic-level picture. Creating complex images, such as one of the quasicrystal itself, can take up to a month, but Fricker says that time could be cut in half if a more efficient pathway could be found to capture each atom.

Fricker also believes the technique could be used to create crystalline catalysts for industrial chemical processes that are more efficient than current methods, making certain compounds faster or less costly to produce. But Fricker thinks other uses may also become apparent over time. “I hope the most interesting uses will be ones that we haven’t even thought of.”