Matthew Ginsberg

Dr. Fill: Crosswords and An Implemented Solver for Singly Weighted CSPs

We described and demonstrated 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.Filll’s performance on crosswords from the American Crossword Puzzle Tournament suggests that it ranks among the top fifty or so crossword solvers in the world.


Matthew (Co-Founder and CEO, On Time Systems Inc.) is a respected and experienced leader in the fields of computational intelligence and optimization mathematics. He received his doctorate in mathematics from Oxford in 1980 at the age of 24 where he remained on as faculty doing research in mathematical physics and computer science. Ginsberg’s continuing interest in artificial intelligence brought him to Stanford where he remained for nine years. At the University of Oregon, Ginsberg co-founded and was first director of the Computational Intelligence Research Laboratory (CIRL). He is the author of numerous publications in search, constraint satisfaction, and partition search, is the editor of “Readings in Nonmonotonic Reasoning,” and the author of “Essentials of Artificial Intelligence.” www.otsys.com