At a crosswords Why solving crosswords is like a phase transition German physicist and crossword fan realized the solving process resembled a type of "percolation problem." Jennifer Ouellette Jan 9, 2025 2:55 pm | 4 Finalists competing in a crossword competition in New York City's Bryant Park in 2019 Credit: Rhododendrites/CC BY-SA 4.0 Finalists competing in a crossword competition in New York City's Bryant Park in 2019 Credit: Rhododendrites/CC BY-SA 4.0 Story textSizeSmallStandardLargeWidth *StandardWideLinksStandardOrange* Subscribers only Learn moreMost crossword puzzle fans have experienced that moment where, after a period of struggle on a particularly difficult puzzle, everything suddenly starts to come together, and they are able to fill in a bunch of squares correctly. Alexander Hartmann, a statistical physicist at the University of Oldenburg in Germany, had an intriguing insight when this happened while he was trying to solve a puzzle one day. According to his paper published in the journal Physical Review E, the crossword puzzle-solving process resembles a type of phase transition known as percolationone that seems to be unique compared to standard percolation models.Traditional mathematical models of percolation date back to the 1940s. Directed percolation is when the flow occurs in a specific direction, akin to how water moves through freshly ground coffee beans, flowing down in the direction of gravity. (In physical systems, percolation is one of the primary mechanisms behind the Brazil nut effect, along with convection.) Such models can also be applicable to a wide range of large networked systems: power grids, financial markets, and social networks, for example.Individual nodes in a random network start linking together, one by one, via short-range connections, until the number of connections reaches a critical threshold (tipping point). At that point, there is a phase shift in which the largest cluster of nodes grows rapidly, giving rise to more long-range connections, resulting in uber-connectivity. The likelihood of two clusters merging is proportional to their size, and once a large cluster forms, it dominates the networked system, absorbing smaller clusters.There's also the more recent concept of "explosive percolation," whereby connectivity emerges not in a slow, continuous process but quite suddenly, simply by replacing the random node connections with predetermined criteriasay, choosing to connect whichever pair of nodes has the fewest pre-existing connections to other nodes. This introduces bias into the system and suppresses the growth of large dominant clusters. Instead, many large unconnected clusters grow until the critical threshold is reached. At that point, even adding just one or two more connections will trigger one global violent merger (instant uber-connectivity).Puzzling over percolationOne might not immediately think of crossword puzzles as a network, although there have been a couple of relevant prior mathematical studies. For instance, John McSweeney of the Rose-Hulman Institute of Technology in Indiana employed a random graph network model for crossword puzzles in 2016. He factored in how a puzzle's solvability is affected by the interactions between the structure of the puzzle's cells (squares) and word difficulty, i.e., the fraction of letters you need to know in a given word in order to figure out what it is.Answers represented nodes while answer crossings represented edges, and McSweeney assigned a random distribution of word difficulty levels to the clues. "This randomness in the clue difficulties is ultimately responsible for the wide variability in the solvability of a puzzle, which many solvers know wella solver, presented with two puzzles of ostensibly equal difficulty, may solve one readily and be stumped by the other," he wrote at the time. At some point, there has to be a phase transition, in which solving the easiest words enables the puzzler to solve the more difficult words until the critical threshold is reached and the puzzler can fill in many solutions in rapid successiona dynamic process that resembles, say, the spread of diseases in social groups. In this sample realization, black sites are shown in black; empty sites are white; and occupied sites contain symbols and letters. Credit: Alexander K. Hartmann, 2024 Hartmann's new model incorporates elements of several nonstandard percolation models, including how much the solver benefits from partial knowledge of the answers. Letters correspond to sites (white squares) while words are segments of those sites, bordered by black squares. There is an a priori probability of being able to solve a given word if no letters are known. If some words are solved, the puzzler gains partial knowledge of neighboring unsolved words, which increases the probability of those words being solved as well.In other words, the probabilities don't start out with long-range correlations, but those probabilities change as easier words get filled in, leading to an acceleration in filling out neighboring words.If youre a solver that is often frustrated and feel like youre not making any progress, this idea of a phase transition can give you a boost of confidence, McSweeney told New Scientist. You might be a lot closer than you realize to solving the whole thing, as long as you can just get a little bit better and jump over that phase transition point.The next step will be to take a closer look at what's happening as the puzzler approaches the critical threshold. Hartmann wonders if the acceleration in filling in correct squares might behave like physical avalanche systems, such as the grains of sand in a sand pile or hourglass. It's a type of spontaneous phase transition also known as self-organized criticality. The sand pile grows, grain by grain, piling up in the shape of a cone. This makes the pile increasingly unstable until adding just a few more grains causes the pile to collapse in an avalanche, forming a wider stable base as the whole process begins again. And smaller avalanches happen more often than larger ones (a power law).Physicists have applied the notion of self-organized criticality to earthquakes, financial markets, traffic jams, biological evolution, how galaxies are distributed in the universe, and even the brain. We'll have to wait and see whether Hartmann's instinct is correct that it might also describe the process of solving a crossword puzzle.Physical Review E, 2025. DOI: 10.1103/PhysRevE.110.064138 (About DOIs).Jennifer OuelletteSenior WriterJennifer OuelletteSenior Writer Jennifer is a senior reporter at Ars Technica with a particular focus on where science meets culture, covering everything from physics and related interdisciplinary topics to her favorite films and TV series. Jennifer lives in Baltimore with her spouse, physicist Sean M. Carroll, and their two cats, Ariel and Caliban. 4 Comments