Is this classic puzzle book game NP-complete?

There is a classic puzzle book game very similar to a crossword puzzle, except a list of words is given and then a $N \times N$ square board made up of unit squares is given, with some squares blacked out just like a cross-word, and some squares have a letter already pre-written in them. The goal is to write each word from the list once and only once in the puzzle, where each word is written either horizontally (left to right) or vertically (top down) into non-blacked out consecutive squares, and when you write a word, the two squares flanking the ends of the word must either be blacked out or off the board. Also for the letters pre-written into some squares, the words written that overlap these squares must respect the pre-written letter.

Now, if we assume a fixed size alphabet for the words, is deciding whether we can fill the board with a valid solution using exactly each word on the list once and only once an NP-complete problem, if the side length of the board is not fixed?

Sorry for answering an old post.

I´ve been thinking about it and i think that the problem with a fixed alphabet is NP-complete as well.

I´m going to reduce positive 1-in-3 SAT to this word problem

Yesterday i was having trouble coming with ideas for solving the problem. I had trouble making each variable different until i looked again at the question and i realized that you allowed having squares with planted symbols. This simplified the reduction a lot. My other idea was to have words of different length for each different variable.

THE REDUCTION

Now i´m going to describe the gadgets we are gonna use:

Variable gadget

We label each variable with a different numerical index and we will have a different number for each variable. We pick the biggest index and we represent the number in binary, we will call this binary chain $n$.

Then we create two different vertical words for each variable. All words will have a length of $3 + |n|$ (Only if we allow duplicate words in the list of words), where $|n|$ is the length of the binary chain $n$.

For instance, let the biggest index be the number $4$. When we transform this number in binary we obtain the chain $100$ in binary, this chain has a length of three. So each variable word will have a length of $6$ in this example.

Now we create two different words for each variable. One word will have the symbol $3$ at the beginning, then the symbol $2$ below, then a binary chain that represents the index of the variable and we pad with zeroes the chain so that it has the same length that chain $n$ and finally the symbol $3$ at the end. Of course the symbols can be changed.

The other word is almost the same but it will have the symbol $4$ instead of the symbol $3$.

For instance, let the biggest index be the number $4$. We will have the following two words for the variable with index $1$:

$320013$ and $420014$

As we see we have padded the binary reperesentation of the number $1$ with zeroes so that it has a length of $|n|$

We have to copy these words many times, we will need one copy of each word for each occurence of a variable in the SAT instance. This will create duplicates in the list of words. We can get rid of the duplicates by adding another binary chain to the binary chain that uniquely identifies the variable. This new chain will uniquely identify each ocurrence of a variable.

To do that, we simply assign each ocurrence of the variable another binary chain and we olace that chain at the end of the binary representation of the variable.

To create this new binary chain first we have to create a different index for each variable, we call the biggest number in each index $n_i$ where $i$ is an identifier for each variable. After that, we transform the number $n_i$ into a binary chain and then we count the length of the chain, we call this number $|n_i|$. Then, for each index, we create a different binary number for each ocurrence of the variable. We pad the number with zeroes until the length of the binary chain becomes $|n_i|$ so that all the words that belong to each ocurrence of the variable have the same length.

This will get rid of duplicates inside the variable words.

For instance, suppose that variable $x_2$ appears three times in the SAT instance.
We create the following words:

$32010013$ $42010014$, $32010103$ $42010104$ and $32010113$ $42010114$

Clause gadget

For each clause gadget, we will create three new horizontal words, each clause word will have a length of $6$ squares (Only if we allow duplicate words in the list of words). These are the words that we will create for each clause:

$535354$, $535453$ and $545353$

We have a different clause word for each possible way of satisfyng the clause, the symbol $4$ represents a literal set to true and the symbol $3$ represents a literal set to false. The number $5$ is used to indicate that it is a clause word.

There will be repeated words in the list of words, we can get rid of the repetitions by using the procedure that we used to uniquely identify the variable words.
That is, we create a different binary chain for each clause and we append each chain to the clause words corresopnding to each clause.
To do that we create a new index for the clauses and we pick the biggest number of the index, we will call this number $m$. We represent $m$ as a binary chain and we call the length of this binary chain as $|m|$. Now, we create a different binary number for each clause, starting with the number 1, and we pad the number with zeroes to make a binary chain that has a length of $|m|$. We append each binary chain to the clause words that belong to the clause.

Now, let´s see a picture of a clause gadget in the board:

This example represents the clause $(x_2 \lor x_3 \lor x_4)$ and the 1 in 3 instance being reduced is $(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4) $

As we see, there are written squares. The vertical columns have written symbols to indicate which literals are inside the cla

StackExchange Computer Science Q#29097, answer score: 6