Solving Crossword Puzzles as Probabilistic Constraint Satisfaction

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

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:

  1. Maximum Probability: Finding the single grid configuration most likely to be entirely correct.
  2. 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.

Figure 6: Comparison of different candidate grids (A-D) showing joint probabilities ($P$), marginal probabilities ($Q$), and converged belief propagation values ($Q^\infty$). The tables show the evolution of word probabilities across iterations.

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

Abstract

Crossword puzzle solving is a classic constraint satisfaction problem, but, when solving a real puzzle, the mapping from clues to variable domains is not perfectly crisp. At best, clues induce a probability distribution over viable targets, which must somehow be respected along with the constraints of the puzzle. Motivated by this type of problem, we describe a formal model of constraint satisfaction with probabilistic preferences on variable values. Two natural optimization problems are defined for this model: maximizing the probability of a correct solution, and maximizing the number of correct words (variable values) in the solution. To the latter, we apply an efficient iterative approximation equivalent to turbo decoding and present results on a collection of real and artificial crossword puzzles.
BibTeX
@inproceedings{shazeer1999solving,
  author = {Noam M. Shazeer and Michael L. Littman and Greg A. Keim},
  title = {{Solving Crossword Puzzles as Probabilistic Constraint Satisfaction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure