# NP-completeness of crossword puzzle

How to prove that this crossword puzzle is NP-complete?

• We have an instance of crosswords in a square grid $$G$$ ​​of size $$m \times m$$.

• We have a set of black boxes $$N$$.

• We have a dictionary of words $$D \subseteq\Sigma^{\ast}$$, where $$\Sigma$$ is a finite alphabet.

The question is whether there is a way to fill in the white boxes ($$G\setminus N$$) so that all the horizontal and vertical words belong to $$D$$. Here we suppose $$|\Sigma|\geq 3$$.

Also note that the reduction should not create a dictionary that is too large.

• You can reduce some version of Planar SAT to your problem. It would require some work. Feb 8, 2020 at 5:10
• I think it's possible to use 3-SAT here, but how to do it?
– tala
Feb 11, 2020 at 22:12
• Why do you think it’s possible? Somebody told you? Feb 11, 2020 at 22:14
• No, I just know that all NP-complete problems get reduced to 3-SAT
– tala
Feb 11, 2020 at 22:19
• Right, but sometimes there isn’t any simple direct reduction. Feb 11, 2020 at 22:21