Proverb: Grid Filling

The algorithm employed by Proverb models grid filling as an optimization problem. In particular, the across and down letter intersections establish constraints on how the grid can be filled, and crossword-puzzle filling is often cited as a constraint satisfaction problem.

However, in our case, we don't just want to find any satisfying set of candidates for the slots; we want the ``best'' fit. We can define ``best'' in several different ways, but currently we attempt to maximize the expected overlap with the creator's solution, in terms of words correct.

Other definitions of ``best'' include maximizing the probability of getting the entire puzzle correct, or maximizing expected letter overlap. The decision to use expected word overlap is motivated by the scoring system used in human tournaments.

Since finding the optimal solution to this problem is intractable, we employ a variety of efficient approximations. These approximations use algorithms similar to those used for turbo codes.

For a complete description see Shazeer, Littman and Keim 99.


Michael Littman (mlittman@cs.rutgers.edu)
Last modified: Thu Apr 29 09:19:46 EDT 1999