As you fill out a crossword, it can abruptly shift from fiendishly difficult to extremely simple. This is similar to the way some physical systems undergo a phase transition 鈥� but compared to them, these puzzles may be mathematically unique.
While solving a crossword one day, at the University of Oldenburg in Germany came up with a personal challenge: he wanted to find enough words to create one large, connected island of letters. Then he realised that he had unintentionally stumbled upon a type of 鈥減ercolation problem鈥�, which was familiar to him from his work as a physicist. The crossword version of this problem, however, seems to be unique.
Percolation refers to processes where bits of matter connect to form currents or flows. Picture water filling up neighbouring pores in a sponge until the liquid drips out, atoms of different metals combining into some complex alloy 鈥� or two words connecting to fill up blank space in a crossword. This process is well studied, so Hartmann knew that it should feature an abrupt transition, called a phase transition, where the crossword goes from very few to very many filled-in words.
Advertisement
鈥淚f you鈥檙e a solver that is often frustrated and feel like you鈥檙e not making any progress, this idea of a phase transition can give you a boost of confidence,鈥� says at the Rose-Hulman Institute of Technology in Indiana. 鈥淵ou might be a lot closer than you realise to solving the whole thing, as long as you can just get a little bit better and jump over that phase transition point.鈥�
Hartmann derived a formula for this transition, based on a mathematical model of the crossword that he devised. Surprisingly, graphing that formula revealed a shape different from all comparable percolation problems.
He says this is because the crossword has one novel ingredient 鈥� each word that you write down makes it easier to find the next one. According to his calculations, the number of words it takes for the puzzle to transition from mostly empty to mostly filled depends on exactly how helpful each word is for finding the next.
McSweeney says that a better mathematical understanding of crosswords may help people who construct them fine-tune each puzzle鈥檚 difficulty.
Hartmann next plans to examine how, as a puzzler nears that phase transition, finding each new word leads to a cascade of more words. He wants to understand whether those cascades can be compared to more physical ones 鈥� like the way grains of sand accumulate into an avalanche.
Physical Review E
