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.
The IR module, in particular, uses a vector space model to determine the semantic proximity between clue terms and potential answers within the CWDB.
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