Abstract
Crossword puzzles represent a unique challenge for artificial intelligence, requiring both deep linguistic understanding and complex constraint satisfaction. We present the Berkeley Crossword Solver (BCS), a system that combines neural question answering with probabilistic inference. By utilizing a dense bi-encoder for answer generation, loopy belief propagation for grid-level constraints, and a generative local search for refinement, the BCS achieved a historic milestone by outperforming all human competitors at the 2021 American Crossword Puzzle Tournament.
Introduction
Crossword puzzles are a "grand challenge" for AI because they sit at the intersection of Natural Language Processing (NLP) and Constraint Satisfaction. Solving a puzzle requires decoding clues that are often intentionally misleading, filled with puns, or reliant on obscure trivia. Furthermore, because words intersect in a grid, every letter must satisfy two different clues simultaneously. This creates a massive search space where a single error can cascade. Previous systems like Dr. Fill relied on hand-crafted heuristics but struggled with the nuanced wordplay that human experts navigate easily.
Methodology
The Berkeley Crossword Solver approaches the problem through a three-stage pipeline designed to balance linguistic intuition with logical consistency.
1. Bi-Encoder QA Model
The system first generates candidate answers for every clue using a "closed-book" bi-encoder based on BERT. This model maps clues and potential answers into a shared vector space. Unlike traditional search engines, it relies on knowledge embedded in its parameters from training on 6.4 million past clue-answer pairs, allowing it to capture the idiosyncratic nature of crossword language.
2. Loopy Belief Propagation (BP)
To reconcile the intersecting constraints of the grid, the system uses Loopy Belief Propagation. BP passes messages between intersecting words to calculate the marginal probability of each letter in each cell. This allows the system to resolve conflicts—for instance, if a high-probability answer for an "Across" clue conflicts with a "Down" clue, BP shifts the probability distribution toward a mutually compatible solution.
3. Local Search with Generative Refinement
The final stage involves a local search to "polish" the solution. The system identifies uncertain areas and proposes small edits (1-2 letter flips). These edits are scored using a second-pass generative model (ByT5), which allows the system to "invent" answers not seen in the training set, such as multi-word phrases or rare crossword fill.
Evaluation and Results
The researchers trained the BCS on a dataset of 6.4 million clue-answer pairs from 26 publishers (1951–2019). The system was evaluated on puzzles from 2020 and 2021, as well as a live performance at the 2021 American Crossword Puzzle Tournament (ACPT).
The BCS represents a significant advancement over previous technology. On New York Times puzzles, it improved exact puzzle accuracy from 71% (Dr. Fill) to 82%. Most notably, at the 2021 ACPT, a hybrid version of the system scored higher than all 1,033 human contestants, marking the first time an automated system has won the event. Despite its complexity, the system remains efficient, solving a typical puzzle in approximately 10 seconds.
Discussion and Limitations
A key insight from this work is that neither pure NLP nor pure search is sufficient; the hybrid approach of bi-encoder "intuition" and BP "logic" is essential. Furthermore, "closed-book" models trained specifically on crossword history outperformed general-purpose web-search models.
However, "themed" puzzles remain a significant challenge. Many crosswords feature gimmicks, such as "rebus" squares (multiple letters in one box) or non-standard reading directions. Because the BCS assumes a standard grid, it is currently limited in handling these creative constructions. Future work will focus on integrating theme-detection modules to address these more complex puzzle types.
This summary is based on "Automated Crossword Solving" by Wallace et al., published in the Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (2022).
Summary updated