Abstract
Crossword puzzles have traditionally been viewed as rigid logic puzzles, but real-world clues often involve significant linguistic ambiguity. This paper redefines crossword solving as a Probabilistic Constraint Satisfaction Problem (PCSP). By applying iterative belief propagation—a technique mathematically equivalent to turbo decoding—the authors developed a solver that prioritizes "expected overlap" (the number of correct words) over finding a single valid grid. The resulting system achieves 89.5% accuracy on New York Times puzzles, demonstrating the power of probabilistic reasoning in structured linguistic domains.
Introduction: Beyond Rigid Constraints
Standard crossword solvers treat the grid as a Constraint Satisfaction Problem (CSP), where variables (slots) must be filled from a domain (dictionary) while satisfying intersections. However, this approach fails to account for the "fuzziness" of clues. For example, a clue like "Small amount [3]" might suggest TAD, JOT, or BIT with varying degrees of likelihood.
A standard CSP cannot distinguish between these candidates beyond their fit in the grid. This paper addresses the gap between probabilistic natural language clues and rigid structural constraints. The goal is to find a solution that respects the grid's geometry while maximizing the likelihood of the chosen words.
Methodology: Probabilistic Optimization
The authors introduce a formal model for PCSPs where each value in a variable's domain is assigned a prior probability $p$ based on the clue. They identify two primary optimization targets:
- Maximum Probability: Finding the single grid configuration most likely to be entirely correct.
- Maximum Expected Overlap: Finding the grid that maximizes the total number of correct words, even if the entire grid is not perfect.
To solve for the latter—a computationally hard (#P-complete) problem—the authors utilize an iterative approximation method. They treat the crossword grid as a cyclic constraint network and apply Pearl’s belief propagation algorithm. By iterating through the grid and updating the "posterior" probability ($q$) of each word based on its neighbors, the system converges on the most likely candidates.
As shown in the figure above, the "Maximum Probability" solution (Grid A, $P=0.350$) is not necessarily the one with the highest expected overlap. Grid C, despite having a lower joint probability, achieves a higher $Q^\infty$ score (3.529), representing a better overall solution in terms of expected correct words.
Evaluation and Results
The solver was evaluated on both artificial and real-world datasets:
- Artificial Puzzles: 600 randomly generated $5 \times 5$ puzzles confirmed the mathematical robustness of the iterative $Q^{(\infty)}$ approximation, which consistently performed within 1% of the theoretical optimum.
- New York Times (NYT): On 70 challenging puzzles, the system achieved an average of 89.5% words correct. This represents a significant improvement over naive approximations (51.8%).
- LA Times: On 50 puzzles with generally more straightforward clues, the solver reached 98.0% accuracy.
Key Insights
- The Power of Loops: Although belief propagation is theoretically exact only for tree structures, it proves remarkably effective on the "loopy" bipartite graphs of crossword grids.
- Search Efficiency: The iterative probabilistic approach enhances search performance. By highlighting "good" candidates early, belief propagation prunes the search space more effectively than standard logic-based methods.
- Implicit Domains: To prevent the solver from failing when a correct word is missing from the initial candidate list, the authors incorporated a letter-bigram model, ensuring every possible letter combination maintains a non-zero probability.
Conclusion and Future Work
While highly successful, the system faces limitations when "expert modules" fail to include the correct answer in the candidate list (occurring in ~2.1% of cases). Future work may involve more sophisticated domain management for massive candidate lists and exploring the convergence properties of belief propagation on even larger, more complex grid structures. By framing crosswords as probabilistic systems, this research provides a robust framework for solving complex, real-world constraint problems.
Summary updated