### Citation

(PDF)
Adam Beacham, Xinguang Chen, Jonathan Sillito, and Peter van Beek.
Constraint programming lessons learned from crossword puzzles.
*Proceedings of the 14th Canadian Conference on
Artificial Intelligence,*
Ottawa, Ontario, 78-87, June, 2001.

### Abstract

Constraint programming is a methodology for solving difficult
combinatorial problems. In the methodology, one makes three
design decisions: the constraint model, the search algorithm
for solving the model, and the heuristic for guiding the search.
Previous work has shown that the three design decisions can greatly
influence the efficiency of a constraint programming approach.
However, what has not been explicitly addressed in previous
work is to what level, if any, the three design decisions can
be made independently. In this paper we use crossword puzzle
generation as a case study to examine this question. We draw
the following general lessons from our study. First, that the
three design decisions---model, algorithm, and heuristic---are
mutually dependent. As a consequence, in order to
solve a problem using constraint programming most efficiently,
one must exhaustively explore the space of possible models,
algorithms, and heuristics. Second, that if we do assume some
form of independence when making our decisions, the resulting
decisions can be sub-optimal by orders of magnitude.

**Return to Publications**