Reduce EXACT 3-SET COVER to a Crossword Puzzle 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$.
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).