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