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:
Problem Name: Exact Cover by 3-Sets
Background: Reduction possible from 3-dimensional matching (one of Karp’s 21 NP-complete problems)
Description:
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.
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:
Also, because there are q horizontal words and each word contains 3 a’s at distinct column indexes, we get the following property:
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.