David W. Binkley
^{1}
Bradley M. Kuhn
` `

binkley@cs.loyola.edu
bkuhn@acm.org
` `

Computer Science Department
Loyola College
4501 N. Charles Street
Baltimore, Maryland 21210-2699

**
**

**KEYWORDS**

Crozzle, NP-complete, complexity

**ABSTRACT**

At the 1996 Symposium on Applied Computing, it was argued that the R-by-C
Crozzle problem was NP-Hard, but not in NP.
The original Crozzle problem is a word puzzle that appears, with a cash reward
for the highest score, in *The Australian Women's Weekly*.
The R-by-C Crozzle problem generalizes the original.
We argue that both problems are, in fact, NP-Complete.
This follows from the reduction of exact 3-set cover to R-by-C Crozzle
and the demonstration of a non-deterministic polynomial time algorithm for
solving an arbitrary instance of the R-by-C Crozzle problem.
A Java implementation of this algorithm is also considered.

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.