How crossing letters turned AI guesses into a crossword solver

At the virtual American Crossword Puzzle Tournament in April 2021, a computer system scored 12,825 points across the seven qualifying puzzles. The best human score was 12,810. The tournament still had a human champion: Tyler Hinman won the separate final. The score comparison covers the seven qualifying grids.[3][4]

The entry combined Berkeley’s new answer model with Dr.Fill, the crossword program developed by Matthew Ginsberg. Their partnership came together quickly. Berkeley graduate student Nicholas Tomlin had reimplemented Dr.Fill as a side project in 2020; the researchers contacted Ginsberg in March 2021 and had an initial connection between their systems two weeks before the tournament.[4]

They could collaborate because a proposed answer came with a probability. Berkeley’s model could supply likely words, while Dr.Fill used its experience of grids and themes to make them coexist. That separation made it possible to improve one part of the solver without discarding the other.[4]

The clue is only one source of evidence

Consider a deliberately simple, invented example. A three-letter answer to “Vessel” might be POT or JAR. If a crossing answer strongly supports T in the final square, POT fits and JAR does not. Nothing about the clue has changed. Another part of the puzzle has supplied evidence that the isolated question lacked.

The later Berkeley Crossword Solver, described in a 2022 paper, developed its own grid-solving machinery. It differs from the tournament hybrid’s reliance on Dr.Fill.[1]

The later system first compares a clue with possible answers using a neural model. It keeps a distribution of possibilities rather than treating its first suggestion as settled. It then passes information between clues and their shared letter squares. A confident answer can strengthen a letter, which in turn changes the relative likelihood of answers running through that square.[2]

This repeated exchange is called belief propagation. The solver uses it to assemble an initial grid, then searches around uncertain letters for improvements. A separate language model helps score the proposed clue–answer combinations during that search. This matters for unfamiliar answers: a fixed inventory of remembered solutions cannot contain every phrase a constructor might invent.[2]

The effect is a change in what counts as a good answer. A word that sounds right in isolation may be expensive to keep if it forces several implausible crossings. A less obvious suggestion can become convincing because it allows the rest of the grid to work.

A nearly correct grid can still be wrong

The paper compares the systems on 234 New York Times puzzles from 2021. Dr.Fill already had high letter accuracy; completely solved grids were a tougher measure.[1]

The difference is 11.2 percentage points for completely solved puzzles, using the rounded values. A half-point gain in letter accuracy can matter because one stubborn square spoils an otherwise excellent grid.[1]

The study covers American-style crosswords, not British cryptics. Unusual themes remained a major source of error: when a constructor changes an entry’s rules, the solver has a further interpretive problem.[1]

That gives the crossword a distinctive place among language tasks. It asks for many answers, but also makes them answer to one another. The decisive clue can arrive sideways.

Report an error or suggest a correction