Next: INTRODUCTION Up: bkuhn's Technical Writings

Crozzle: an NP-Complete Problem


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.















Next: INTRODUCTION Up: bkuhn's Technical Writings

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.