Dr.Fill: Crosswords and an Implemented Solver for Singly Weighted CSPs
  We describe Dr.Fill, a program that solves American-style crossword puzzles.
From a technical perspective, Dr.Fill works by converting crosswords to
weighted CSPs, and then using a variety of novel techniques to find a solution.
These techniques include generally applicable heuristics for variable and value
selection, a variant of limited discrepancy search, and postprocessing and
partitioning ideas. Branch and bound is not used, as it was incompatible with
postprocessing and was determined experimentally to be of little practical
value. Dr.Fillls performance on crosswords from the American Crossword Puzzle
Tournament suggests that it ranks among the top fifty or so crossword solvers
in the world.
