Reduce EXACT 3-SET COVER to a Crossword Puzzle

Question

I have an assignment where I have to prove that solving a crossword puzzle is an $NP$-complete problem by reducing from EXACT 3-SET COVER. I have more or less given up at this point. If anyone could give me a hint or know where to find the proof, it would be much appreciated.

Problem: [${\bf CrossWordPuzzleConstruction}$]

Input: Given are an alphabet $\Sigma$ not containing the symbols "blank" or "#", a non-empty set of strings $S=\{s_1,\dots,s_m\}$ over $\Sigma$, and an $n\times n$ matrix $A$ for a non-negative integer $n$. The entries in $A$ are either "blank" or "#".

Output: YES if the blank entries in $A$ can be filled with letters from $\Sigma$ in such a way that the result is a crossword puzzle with strings from $S$. That is, every maximal horizontal or vertical sequence in $A$ consisting of letters from $\Sigma$ is a string from $S$ when read left-to-right respectively downwards. The same string may occur more than once.

We call the problem ${\bf CPC}$ for short.

Example: $\Sigma=\{a,b,c\}$, $S=\{aa,bb,cac,ab,cab,ca,a,ac,bba,aab,bab\}$,

The answer to this input is YES as the following solution shows:

Problem: [${\bf ExactThreeCover}$]

Input: The set $X=\{1,2,\dots,n\}$ where $n=3q$, $q\geq1$, and a collection $\mathcal{C}=\{C_1,C_2,\dots,C_m\}$ of subsets of $X$ of sixe $3$. That is, for $i\in\{1,\dots,m\}$, we have $C_i\subseteq X$ and $|C_i|=3$.

Output: YES if there exists a set $\mathcal{A}\subseteq\mathcal{C}$ such that the elements of $\mathcal{A}$ are a partition of $X$, i.e., $\cup_{C_i\in \mathcal{A}}=X$ and $C_i\cap C_j=\emptyset$ for $C_i,C_j\in\mathcal{A}$ and $i\neq j$.

Answer 1

Since you are so interested in solving this assignment to hand in and be applaused by the whole class.

I give you another answer.

Reduce from X3C (Exact 3-Set Cover) as required.

We will construct a table as follows:

The leftmost column will be forced to be (solely by its maximum length)

$\star\\ \star\\ \star\\ 1_{row}\\ \star\\ \star\\ \star\\ \star\\ \star\\ 2_{row}\\ \star\\ \star\\ \star\\ \star\\ \star\\ 3_{row}\\ \dots $

The uppermost row will contain the solution (a subcollection of $3$-sets).

$\#\#\#1_{col}\star\star\star\star2_{col}\star\star\star\star3_{col}\#\#\dots\#\#\#$ to denote that we choose a $3$-set that contains $1$, $2$ and $3$.

Now, all that we need is to make sure that our solution which appear in the uppermost row is feasible. It means that for each $i_{row}$, if we "beam" from its position (in the first column) to the right, we will meet $i_{col}$ exactly once (in fact, we only need to assure at most once).

To guarantee this, we create zig-zag tunnel like this:

- ---
| | |
| | |
---- --- ...

To be able to cross a different column item, we add these words $i_{row}<i_{row}j_{col}>i_{row}$ where $<i_{row}j_{col}>$ is a single symbol, for every $i\neq j$. And, similarly, for the column item, these words $j_{col}<i_{row}j_{col}>j_{col}$

To be able to meet the same column item (and never again), we add these words $i_{row}<i_{row}i_{met}>i_{met}$, for all $i$. Similarly, for the column item, these words $i_{col}<i_{row}i_{met}>i_{col}$.

Note that, $i_{met}$ are deemed to belong to the rows only.

To be able, to continue after crossing the same column item, and never meets same column item again, we add these words $i_{met}<i_{met}j_{col}>i_{met}$, for every $i\neq j$. And, similarly, for the column item, $j_{col}<i_{met}j_{col}>j_{col}$.

Lastly, to be able to go through the tunnel, add all these word $x\star x$ for all symbol $x$ that appears so far.

Answer 2

A reduction from PLANAR 3-SAT with bounded occurrences is more viable.

The upper bound of occurrences should be $3$ for each variables $x_i$ (two positive and one negative OR two negative and one negative).