Solving Crosswords with PROVERB

Michael L. Littman, Greg A. Keim, Noam M. Shazeer

Abstract

PROVERB is a probabilistic crossword solver that addresses the dual challenges of clue interpretation and grid constraints. By employing an ensemble of thirty specialized "expert modules" for candidate generation and a probabilistic inference engine for grid filling, PROVERB bridges the gap between linguistic ambiguity and combinatorial search. On a standard New York Times puzzle, the system achieved an 88.5% accuracy rate, demonstrating the efficacy of combining large-scale information retrieval with constraint satisfaction.

Introduction

Historically, AI research treated crossword puzzles primarily as Constraint Satisfaction Problems (CSPs). These approaches focused on the mechanics of fitting a predefined word list into a grid. However, the true difficulty of crosswords lies in the "broad-coverage" problem: interpreting clues that utilize puns, trivia, synonyms, and cultural nuances. PROVERB (the "probabilistic cruciverbalist") was developed to automate this interpretation process, moving beyond simple grid-filling to handle the complex language found in high-quality puzzles like those in The New York Times.

Methodology

PROVERB operates through a two-phase architecture: candidate generation and probabilistic grid filling.

Candidate Generation: The Expert Modules

Rather than relying on a single algorithm, PROVERB utilizes a committee of approximately 30 "Expert Modules." Each module is designed to tackle specific types of clues using different data sources and heuristics:

  • CWDB Modules: These query a database of over 350,000 historical clues and solutions (the Crossword Database).
  • Information Retrieval (IR): This module leverages online encyclopedias and full-text sources to find answers for trivia-based clues.
  • Domain-Specific Databases: Specialized modules target areas like geography, music, and film (e.g., IMDb).
  • Syntactic and Transformation Modules: These handle structural clues, such as "fill-in-the-blank" formats, and learn common crossword substitutions.
Examples of clues and candidate answers generated by PROVERB's expert modules.

The IR module, in particular, uses a vector space model to determine the semantic proximity between clue terms and potential answers within the CWDB.

The Information Retrieval module combines vector space models with historical data to identify relevant candidates.

Probabilistic Grid Filling

Once the experts provide a list of candidate words with associated confidence scores, the Solver component takes over. The grid is modeled as a belief network where the goal is to find a word configuration that maximizes the joint probability of all answers while satisfying the physical constraints of the intersecting letters. This probabilistic approach allows the system to perform error correction; a lower-confidence candidate may be selected if it is the only word that fits the intersections of several high-confidence answers.

Results and Discussion

The system was evaluated using a 70-clue New York Times puzzle from October 1998.

  • Initial Solving: Prior to grid constraints, the expert modules placed the correct answer in the top ten candidates for roughly 47% of the clues.
  • Final Performance: After the probabilistic solver integrated the grid constraints, PROVERB correctly solved 62 out of 70 clues (88.5%).

These results highlight several key insights. First, crosswords are fundamentally an ensemble task; no single strategy suffices. Second, the "meta-language" of crosswords—the tendency for certain clues to recur or follow predictable patterns—can be effectively mined from historical data. Finally, the probabilistic solver acts as a robust filter, using the structural logic of the grid to resolve linguistic ambiguities.

Limitations

Despite its success with American-style puzzles, PROVERB faces limitations. It is not designed for "cryptic" crosswords, which rely on intricate wordplay rules rather than synonyms and trivia. Furthermore, the system's performance is heavily tied to the breadth of its database (CWDB). While it can generalize, highly original or creative puns that lack historical precedent may still pose a significant challenge.

Summary updated

Abstract

We attacked the problem of solving crossword puzzles by computer: Given a set of clues and a crossword grid, try to maximize the number of words correctly filled in. PROVERB, the probabilistic crueiverbalist, separates the problem into two, more familiar subproblems: candidate generation and grid filling. In candidate generation, each clue is treated as a type of query to an information retrieval system, and relevant words of the correct length are returned along with confidence scores. In grid filling, the candidate words are fit into the puzzle grid to maximize an overall confidence score using a combination of ideas from belief network inference and constraint satisfaction. For our demonstration, we will have an interactive version of the candidate-generation process available via the web, and will also give people an opportunity to go head-to-head against PROVERB in solving complete puzzles.
BibTeX
@inproceedings{littman1999solving,
  author = {Michael L. Littman and Greg A. Keim and Noam M. Shazeer},
  title = {{Solving Crosswords with PROVERB}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure