Solving Crossword Puzzles as Probabilistic Constraint Satisfaction

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Constraint Satisfaction Problems

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 provide 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. We provide an efficient iterative approximation for the latter based on dynamic programming and present very encouraging results on a collection of real and artificial crossword puzzles.