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.

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?

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 = {x_{1},x_{2},...,x_{3q}}. For each subset L ∈ S, say L = {x_{i},x_{j},x_{k}}.
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.

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.

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.

- 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.