Why solving crosswords is like a phase transition

Most 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 percolation—one 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.

Read full article

Comments