The R-by-C Crozzle problem, introduced at the 1996 ACM Symposium on Applied Computing , is a generalization of the Crozzle problem found in The Australian Women's Weekly. A Crozzle is a word puzzle played on a 10x15 grid. Words from a supplied list are placed on the grid subject to the following rules:
A Crozzle is scored as follows: 10 points for each word placed plus points for each letter that appears at the intersection of two words. Letters have the following point values:
Figure 1 shows two solutions to a simple Crozzle. Algorithms for automatically finding good solutions to Crozzles have appeared in the literature [5,3].
The R-by-C Crozzle problem, introduced by Gower and Wilkerson to study the complexity of the original, generalizes the Crozzle problem as follows: in addition to a list of words, an instance of the R-by-C Crozzle problem has as input and , the number of rows and columns in the grid. Thus the original Crozzle problem is R-by-C Crozzle with and .
Gower and Wilkerson argue that R-by-C Crozzle is NP-Hard, but not in NP. Unfortunately this says nothing about the complexity of the original problem as it is possible that restricting R to 15 and C to 10 would place it in NP. Section 2 demonstrates that R-by-C Crozzle is in fact in NP and thus an NP-Complete problem. This implies that the original (more restrictive) Crozzle problem is also NP-Complete.
One technical note: the words supplied as part of a Crozzle are normally English words. There are a finite number of English words; thus, one could, in theory, precompute all possible Crozzle solutions giving a constant time bound to the problem. To study its complexity, we generalize the input to include arbitrary words taken from some finite alphabet.
Copyright © 1997 Bradley M. Kuhn, David W. Binkley.
Verbatim copying and distribution of this entire paper is permitted in any medium, provided this notice is preserved.