The R-by-C Crozzle problem, introduced at the 1996 ACM Symposium on Applied
Computing [2], 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:

- 1.
- Not all of the words need to be placed.
- 2.
- All placed words must fit completely on the grid.
- 3.
- The intersection of two words must be at a shared letter.
- 4.
- No two words may be adjacent (unless the adjacent parts are covered by Rule 3) or placed end-to-end.
- 5.
- The words must form a single connected unit.

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.