文档介绍：A ic-Algorithm Approach to
Solving Crossword Puzzles
t Management Information Systems Department
University of Arizona
Tucson, Arizona
******@. edu
$GrifithUniversit
Queensland, Austr Jia
cadharr lffi! .
puzzles (described below) are periodically pub-
Abstract lished in magazines and solved by readers; while
no machine generated solution has yet bettered
This work describes attempts to solve crossword those of the readers. Traditional tree spanning
puzzle variants, known as go-words, using a prob- algorithms continue to be applied to the prob-
abilistic approach in the form of a ic algo- lem, with the ingenuity of individual researchers
rithm. The go-words puzzle is defined by a fixed expandin the search envelope slightly with each
rid, which includes black squares, and a given iteration f Harr92]. It is easy to determine that
fexicon containing words of a specified length. This increases in the size and/or ad plexity
~roblem, like similar crossword puzzle problems, of individual puzzles can move them quickly out
plete. The size of the search space for of r,each of deterministic machine SO1utio s once
problems of reasonable size, however, makes it a again. It has been shown that the size oft i e sohr-
difficult candidate for attempts to generate solu- tion set can be counted [Harr90]; and for the tar-
tions through t