Crossword Puzzles as Constraint Satisfaction Problems
Russell Steinthal <rms39@columbia.edu>
Final Project Report for COMS W4721: Advanced Intelligent Systems (Prof.
Siegel)
Introduction
Crossword puzzles, in addition to being a hobby of potentially millions
of people around the world, are an excellent realworld example of
a constraint satisfaction problem. A solution to a crossword puzzle,
after all, is an assignment of words to a grid such that each meets a number
of constraints: a semantic constraint provided by the clue, a length constraint
provided by the grid, and constraints on its its letters provided by the
words which it overlaps in the grid. Similarly, the construction
of a puzzle is based on similar constraints, although the application is
somewhat different. This paper describes an attempt at modeling those
constraints formally and using that model to implement systems to solve
and generate puzzles.
Ideally, any solution to the crossword puzzle problem would first provide
a generalpurpose constraint satisfaction implementation which would be
applicable to other domains. Unfortunately, to date I have been unable
to achieve such a general solution, although I have had limited success
with crosswordspecific solutions. This paper, therefore, describes
the models I have created and the successes (and failures) I have had trying
to implement it.
Crossword Puzzle Models
Early in my work on this project, two potential models for the problem
suggested themselves, one based on words, and the other based on characters.
A word based approach
The wordbased approach is based on a simple implementation of the general
constraintsatisfaction framework (such as that suggested by Russel and
Norvig), namely an assignment of values to a set of variables such that
each meets all the specified constraints. For crossword puzzles,
the variables are the words which need to be filled in, one variable for
each of the words in the puzzle solution. The grid also provides
the initial constraints for each word, such as the number of letters, what
overlap relationships the word has with other words in the grid, etc.
The basic rule that whenever two words overlap, they must share the same
letter in the overlap position must also be encoded in the system.
Finally, a dictionary provides the overall constraint that any valid value
for a variable must be in the dictionary. (Of course, that limits
the crossword puzzles which can be solved, since most puzzles use at least
one twoword phrase or proper name; from a theoretical perspective, however,
one could construct a sufficiently large dictionary to avoid this problem.)
The advantage to this approach is that as a direct implementation of
the generic CSP model, there are algorithms which are known to work,
and which would be extensible to other problems. However, I was unable
to come up with a suitable representation for the constraints listed, and
so began considering other models.
A characterbased approach
This approach is based on another view of the crossword puzzle, and suggests
different algorithms. Instead of looking at a solution as a set of
words, it views the grid as a matrix of squares, and a solution, therefore,
is an assignment of characters to grid squares such that each string of
characters, read across or down, is a word in the dictionary.
Constraints on the length of words are represented by marking appropriate
squares in the grid with "stop" flags, indicating that no letter goes in
that square, and scanning should stop (i.e. whatever string has been constructed
to that point should be checked against the dictionary). This is,
obviously, a direct translation of the blackened squares on a traditional
crossword puzzle.
This seemed like a simpler to implement approach, so I chose to begin
with it. It also has the advantage that the time to solution is bounded,
since each square can only have one of 26 possible values; unfortunately,
the bound is very high for any reasonably sized grid, so heuristics are
necessary to reduce the number of possibilities.
A note on natural language constraints
Neither of the models presented above considers the language constraints
on a puzzle solution, namely that each word "answer" the associated clue.
To do so would require not only a complete semantic database (such as WordNet),
but also a system which could parse the clues and generate queries into
the database; this is beyond the scope of this project, although it could
be added by inserting an additional constraint, whether in the set of constraints
for the first approach, or as a check in the scanning stage of the second
approach.
A somewhat more limited use of naturallanguage processing, however,
could be of more immediate use. In most puzzles, clues and their
answers fill the same syntactic role. For example, if the clue is
a noun phrase, the solution is usually a noun; verb phrases and verbs similarly.
If the clues were run through a syntactic analyzer such as CASS, it should
be possible to generate partofspeech hints (or constraints, depending
on one's degree of confidence in this rule)
A basic crosswordsolving algorithm
A large part of the research on this project centered around the creation
and refinement of the following algorithm for filling in a crossword grid
(under the characterbased model described above). It takes as input
a grid and a word list; with minor variations, the same algorithm
can be used either to solve a puzzle (in which case the grid is input with
"stops" already in place, and the word list is (possibly a subset of) the
dictionary) or to generate a puzzle solution (in which case the grid is
initially empty and the word list contains the words to fill into the grid).
Note that a subgrid, as used in the algorithm, is a section of the grid
space whose upper left square is the first letter of both its horizontal
and vertical words; the subgrid then extends to all squares which are part
of words which intersect either the horizontal or vertical word starting
from the initial position.

Initialization: Set all the squares in the grid to their unconstrained
state, that is all character values are possible. (For solving purposes,
this is AZ; for generation, AZ plus a stop indicator, such as NUL.)

Repeat the following for each subgrid:

For each of the possible character values of the initial
(upper left) position, get all words from the word list which begin with
the given character, and which satisfy the length constraints for the down
and across words, respectively. If there is not at least one word
which satisfies the length and initial letter constraints for each of the
two words (that is, there must be at least one valid across word and one
valid down word), move to the next character value. Otherwise:

"Write in" each of the words which were determined to meet the across
criteria into the grid, moving righward from the initial cell as you go.
For each character written, maintain a reference to what word caused it
to be written in.

If at any point a letter cannot be written into a cell because it is no
longer a possible value for the cell, remove the current word from the
grid and proceed to the next word.

Repeat the above two steps for the down words, starting from the initial
position and moving downward.

Move to the cell to the right of the initial position. For each character
in the list of possible values, find all words which meet the length and
initial letter constraints (i.e. start with the correct letter and are
the proper length). Call this list words.

If words is empty, delete the current character from the list of
possible values. Propagate the deletion backwards and forwards in
the grid by removing the word which caused the deleted character to be
written in. Repeat as necessary; if a cell ever loses all of its
possible values, terminate the algorithm and return FAIL.

"Write in" each of the words, as above. If a letter must be written
into a cell for which it is not a possible value, remove the current word
and propagate the changes.

Repeat the above step for each row of the grid, for the length of the initial
down word. This should completely traverse the subgrid.

When all subgrids have been filled in, the grid should contain
a representation of all possible solutions. Output either one or
all possible solutions using one of any number of algorithms for
enumerating the solutions. (The grid consists of a collapsed tree
of possible solutions, with each cell representing all the possible values
for that cell.)
Results
While the algorithm above is believed to be correct, it is extremely inefficient
due to the complexity of the problem. Heuristics, such as considering
only a subset of the dictionary (trimmed at the longest word in the
puzzle, for instance) or the partofspeech heuristics mentioned above
can be used to reduce the number of possibilities which must be considered,
but the algorithm is still at least polynomial time.
In addition, simple tasks like loading a complete dictionary can be
timeconsuming: on the author's machine (a Pentium90), loading /usr/dict/words
into the inmemory data structure took in excess of 20 minutes. (I
am aware that running the algorithm on a full /usr/dict/words would take
an exorbitant amount of time; it is provided only for reference, and as
an example of one of my earlier (foolish) experiments in this project).
Finally, I do not yet have a working implementation of this algorithm,
in large part because its time constraints make running test cases fairly
difficult. A pen and paper implementation, however, shows that it
should work.
Conclusion
Although an algorithm does exist to solve and generate crossword puzzles
using constraint propagation, its time and space complexity is at least
polynomial. Future work, therefore, should focus on either finding
a linear time algorithm (which I believe to be unlikely) or on heuristics
to reduce the search space; as indicated above, the use of natural language
rules to partition the dictionary might be one of the more promising ways
of doing so.