Crossword Puzzles

Crossword puzzle generation problems have been used for the evaluation of algorithms and heuristics for CSPs [Ginsberg, Frank, Halpin, TorranceGinsberg et al.1990,Beacham, Chen, Sillito, van BeekBeacham et al.2001] and binary encodings of non-binary problems [Bacchus van BeekBacchus van Beek1998,Stergiou WalshStergiou Walsh1999]. In crossword puzzle generation we try to construct puzzles for a given number of words and a given grid which has to be filled in with words. This problem can be represented as either a non-binary or a binary CSP in a straightforward way. In the non-binary representation there is a variable for each letter to be filled in and a non-binary constraint for each set of $k$ variables that form a word in the puzzle. The domain of each variable consists of the low case letters of the English alphabet giving a domain size of 26. The allowed tuples of such a constraint are all the words with $k$ letters in the dictionary used. These are very few compared to the $26^k$ possible combinations of letters, which means that the constraints are very tight. In the DE there is a variable for each word of length $k$ in the puzzle and the possible values of such a variable are all the words with $k$ letters in the dictionary. This gives variables with large domains (up to 4072 values for the Unix dictionary that we used in the experiments). There are binary constraints between variables that intersect (i.e. they have a common letter). In the HVE there are all the original variables as well a set of dual variables, one for each non-binary constraint.