Constraint Satisfaction with Probabilistic Preferences on Variable Values
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 de ned 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 e cient iterative approximation for the latter based on dynamic programming and present very encouraging results on a collection of real and arti cial crossword puzzles.