DR.FILL: CROSSWORDS AND AN IMPLEMENTED SOLVER FOR SINGLY WEIGHTED CSPS

MATTHEW GINSBERG

On Time Systems

We describe and demonstrate 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 ideas. Branch and bound is
not used, as it was incompatible with postprocessing and was determined
experimentally to be of little practical value. Dr.Fill's performance on
crosswords from the American Crossword Puzzle Tournament suggests that it
ranks among the top hundred or so crossword solvers in the world.

BIO

Matthew L. Ginsberg received his doctorate in mathematics from Oxford in
1980 at the age of 24. He remained on the faculty in Oxford until 1983,
doing research in mathematical physics and computer science; during this
period, he wrote a program that was used successfully to trade stock and
stock options on Wall Street.

Ginsberg's continuing interest in artificial intelligence brought him to
Stanford in late 1983, where he remained for nine years. He then went on
to found CIRL, the computational intelligence research laboratory at the
University of Oregon, which he directed until 1996. He remained at CIRL
until 1998, when CIRL spun off On Time Systems, a commercial entity
focusing on scheduling and routing technology. Ginsberg has been the CEO
of the company since its formation and is currently its chairman as well.

Ginsberg is also the chairman and CEO of Green Driver, Inc., a sister
company to On Time Systems that focuses on using real-time traffic and
signal information to improve driver safety, fuel efficiency, and the
driving experience generally.

Ginsberg's present research interests focus on constraint satisfaction. He
is the author of numerous publications in this area, the editor of
"Readings in Nonmonotonic Reasoning," and the author of "Essentials of
Artificial Intelligence," both published by Morgan Kaufmann. He is also
the author of the bridge-playing program GIB, which made international
news by finishing 12th in the world bridge championships in Lille, France,
and the author of Dr.Fill, a crossword-solving program that made national
news by participating in the American Crossword Puzzle Tournament in March
of 2012.