Solving Crossword Puzzles as Probabilistic Constraint Satisfaction
Lists
Only you see this
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},
}Loading related content...