David W. Binkley1
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.