R-BY-C CROZZLE IS      NP-COMPLETE

To prove that a problem $X$ is NP-Complete it is sufficient to show that (1) $X$ is NP-hard and (2) $X$ is in NP [4]. Problem $X$ is NP-hard if there is a deterministic polynomial-time reduction from some problem in NP to $X$. Since reductions compose, this implies that every problem in NP can be reduced to $X$. Problem $X$ is in NP if all instances of $X$ can be solved in non-deterministic polynomial time.

Gower and Wilkerson argue that R-by-C Crozzle is NP-hard, but not in NP. They prove R-by-C Crozzle is NP-hard by reducing the exact 3-set cover problem to the R-by-C Crozzle problem. The exact 3-set cover problem is defined as follows: For a set $S$ and a set $F$, a collection of sets each having three elements from $S$, a solution to the exact 3-set cover problem is a subset of $F$ where $\bigcup F = S$ and each member of $S$ appears in exactly one element of $F$ [1].

THEOREM 1.  [2]. Exact Cover by 3-sets reduces to R-by-C Crozzle.

Gower and Wilkerson also argue that R-by-C Crozzle is not in NP because

``the minimum amount of work required is an examination of each square (i.e., on the order $R \times C$). The number of steps is dependent upon the values of $R$ and $C$ rather than the size of the inputs. Since there is no relationship between $R \times C$ and the number ($n$) of words in the list, there cannot be a polynomial-time algorithms to check possible solutions for all values of $R$ and $C$, and $n$. Therefore R-by-C Crozzle is not in NP.''

We argue that R-by-C Crozzle is in fact in NP by showing that the number of steps taken to find the highest scoring solution is dependent on the size of the input and not on $R$ and $C$. Recall that the words placed on the grid must form an interconnected unit. A bound is found not in the number of words, but in the lengths of the words. Let $length$ be the sum of the lengths of the input words. Neither the width nor the height of the words placed on the grid can exceed $length$. Thus at most a $length ^2$ portion of the $R \times C$ grid need by considered². This relationship is used in the following theorem.

THEOREM 2. R-by-C Crozzle is NP-complete.

PROOF. Theorem 1 proves the R-by-C Crozzle is NP-hard. What remains is to prove that R-by-C Crozzle is in NP. One way of doing this is to provide a non-deterministic polynomial time algorithm for solving R-by-C Crozzles. The following algorithms solves an instance of the R-by-C Crozzle problem in non-deterministic polynomial time.

1

Read in $R$, $C$, and the Words $w_i$.

2

Compute length = $\sum \vert w_i \vert$.

3

Let R = minimum(R, length) and

C = minimum(C, length).

4

Non-deterministically pick those words that will be used in the solution.

5

Non-deterministically assign each word a starting row, starting column, and orientation (UP-and-DOWN or BACK-and-FORTH).

Steps 1, 2, 4, and 5 take linear time (steps 4 and 5 make a linear number of non-deterministic choices). Step 3 takes constant time.

$\Box$

Since the original Crozzle problem found in The Australian Women's Weekly is a restricted version of R-by-C Crozzle, we have the following corollary:

COROLLARY. The original Crozzle problem is NP-complete.

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.