My Crossword Generation Tools

Reduction of Crossword Puzzle Construction

Given that Exact Cover by 3-Sets is NP-complete, this proof will show that Crossword Puzzle Construction is also NP-complete. By first (1) defining the problems, (2) showing the reduction, (3) proving correctness by proving (3.1) the implication, then (3.2) the reverse implication.

1 Defining the Problems:

  Problem Name: Crossword Puzzle Construction

Background: A variant of this problem is listed as GP14 in Computers and intractability : a guide to the theory of NP-completeness by Michael Garey and David Johnson

Description:

1.
Input:
(a)
A fixed alphabet Σ
(b)
A set of words W over Σ
(c)
An n by n boolean matrix A
2.
Question: Can we fill all 0’s of the matrix A with words from W so that every maximally contiguous horizontal and vertical sequence forms a word from W?
3.
A fill is defined as a partial assignment of cell indices to letters from Σ such that the assignment is defined for every cell labelled 0.

Problem Name: Exact Cover by 3-Sets

Background: Reduction possible from 3-dimensional matching (one of Karp’s 21 NP-complete problems)

Description:

1.
Input:
(a)
A set X containing 3q elements | q
(b)
A set S, where S is a subset of P(X) |∀L S,|L| = 3
2.
A set C is an exact cover by 3-sets of X if each element of C has size 3, the union of C = X, and C’s elements are pairwise disjoint.
3.
Question: Can we find an exact cover by 3-sets of X that is a subset of S?

2 Showing the Reduction:

Reduction of Exact Cover by 3-Sets to Crossword Puzzle Construction:

Let an input X, S for Exact Cover by 3-Sets be given. Define Σ = {a,b}.

Now we must construct W.

First we’ll label elements in X = {x1,x2,...,x3q}. For each subset L S, say L = {xi,xj,xk}. Add to W a string of length 3q such that there are a’s in the ith, jth, and kth positions, and b’s elsewhere.

Now, construct q strings, each of length q, with a single a in each position, and b’s elsewhere. For example, if q = 3, we would add ‘abb’, ‘bab’, and ‘bba’ to W.

Finally, we build our n by n matrix, A. In order to do this, first let n = 3q. Let the first q rows all be 0’s (blank squares), and the final 2q rows all be 1’s (shaded squares).

Now we have our input for Crossword Puzzle Construction, Σ, W, and A.

3 Proof of Correctness:

3.1 Implication:

Now we must prove that if Crossword Puzzle Construction accepts the input, then there is an Exact Cover by 3-Sets.

If there is a fill for our matrix A from our word list W, then all of the horizontal words must contain exactly 3 a’s because the contiguous horizontal blocks of 0’s have length 3q. Also, all of the vertical words must contain exactly 1 a because the contiguous vertical blocks have length q.

Next, because the vertical words have only 1 a, we get the following property:

1.
No two horizontal words can have a’s at the same column index.

Also, because there are q horizontal words and each word contains 3 a’s at distinct column indexes, we get the following property:

2.
There are exactly 3q a’s in the fill of the matrix where one a appears in each column.

Now, by relating column indexes in A to elements of X, we know that each horizontal word in A (which contains 3 a’s) is associated with a 3-element set in S. Let C denote the set of all 3-element sets that are associated with horizontal words in A.

Because of property (1), the elements of C are pairwise disjoint.

Because of property (2), the union of C equals X.

Therefore, if Crossword Puzzle Construction accepts the input, then there is an Exact Cover by 3-Sets.

3.2 Reverse Implication:

Finally, we must prove that if there is an Exact Cover by 3-sets, then Crossword Puzzle Construction will accept the input.

Suppose that there exists an exact cover by 3-sets of X that is a subset of S.

Let C denote such an exact cover by 3-sets.

By relating elements of X to column indexes in A, we can associate each 3-element set in C with a word of length 3q that contains 3 a’s.

Fill A with such words appearing horizontally in any order.

Because the elements of C are pairwise disjoint and the union of C equals X, we know that each column from the fill of A will have exactly 1 a. As a result, all columns of A are filled with valid words in W.

Therefore, this is a valid fill for the Crossword Puzzle Construction problem. With that, our proof is complete and Crossword Puzzle Construction is shown to be NP-complete.

4 Further observations about hard instances:

1.
There are repeated words: the vertical words of length q with 1 a are all used three times.
2.
Words have two lengths: the words are either of length q or 3q.
3.
Words are very similar to each other: Any two words of length q differ in exactly 2 positions and any two words of length 3q differ in at most 6 positions.
4.
Grid is an open rectangle.
5.
Alphabet is binary.