Is this classic puzzle book game NP-complete?

Question

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?

Answer 1

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 clause. The end and the beginning of the column are blank squares. This lets the player choose the value of the variable. The marked symbols in the horizontal row force the player to put a clause word in that row. Because all clause words have only a single symbol $4$ that means that only one of the literals that is inside the clause gadget can be set to "true".

If we don´t allow duplicates inside the list of words we will have to modify the image.

The clause row in the image will become: $5b5b5b10$ and the literal columns will be, from left to right:

$b201010b$, $b201110b$ and $b21001b$

Where the symbol $b$ means blank square

See an example:

Variable consistency gadget

This is a gadget that ensures that the player can only asign the same value for all literal columns of a variable.

We will have a new gadget for each variable

We will create two new words for each gadget.

The length of the word will depend on the number of ocurrences of a variable. The length of a word will be $2 * k$ where $k$ is the number of ocurrences of a variable. So if variable $x_2$ appears two times in the sat instance, the words will have a length of four. One of the two words is formed by repeating the chain $63$ $k$ times, where k is the number of occurrences of the variable. The other word is formed by repeating the chain $64$ $k$ times, where k is the number of occurrences of the variable in the SAT instance being reduced.

For instance if a variable $x_2$ has two ocurrences, the words that belong to the corresponding variable assignment gadget will be:

$6363$ and $6464$

If we want to avoid repeated words, notice that each consistency gadget belongs to a different variable. So we can append the binary chain that identifies each variable to the two words that we created for this gadget.

Now let´s see an example picture of this gadget:

This gadget is for the variable $x_2$ 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 two horizontal rows, the symbols written inside the rows make sure that we can only place words containing those symbols, those words are the words that we created for this gadget. In one of the rows, we see that there are two columns coming into it, because of the symbols that are placed in the columns we make sure we can only place variable words. Because the only words we can only place on the variable consistency row have only the symbol $3$ or only the symbol $4$ in them, we force the player to place all variable words with that symbol inside the gadget. This means that the only variable words that are available to be placed inside the clause gadgets have only the symbol $3$ or only the symbol $4$. We can place the remaining word of this gagdet in the other row

If we don´t allow duplicates in the list of words, the words inside the example picture will be:

For the rows:

$6b6b010$ and $6b6b010$

For the columns:

$b201001b$ and $b201010b$

Where the symbol $b$ means blank square

See an example:

Clause dump gadget

This is a gadget created to place the unused clause words. To do that, we have only to place two rows for each clause word in an empty part of the board. These rows are not connected to any other row or column.

With this we finish the reduction, as we claimed we only need 6 symbols for the reduction.

Example

If the previous explanation was confusing, here is an example picture of an instance of positive 1 in 3 SAT that has been reduced to this word problem:

If we disallow repeated words:

The instance that has been reduced is:

$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4) $

Answer 2

I think the following reduction from Directed Hamiltonian path works:

Given a graph $G=(V,E)$ and a two vertices $s,t\in V$, we output the following puzzle:

The alphabet is $V\cup \{*\}$, with $*$ being some symbol not in $V$.

The words are $v*v$ for every $v\in V$, and $vu$ for every edge $(u,v)\in E$.

The board consists of two parts. The first looks like $|V|$ horizontal "stairs" of length 3, stacked on top of each other, as depicted here:

The second part consists of $|E|-(|V|-1)$ disjoint spaces of length 2.

Also, we set in the first (bottom) step of the stairs the word $s*s$ (and remove it from the word list), and in the last step we put $t*t$.

Now, in order to fill the stairs, only vertex-words can be put within the steps, and in order to connect two vertices, an edge word must be put between them, which corresponds to an existing edge in the graph. The unused edges can be put in the second part of the board. The second direction is trivial.

I think this works (the correctness proof I sketched is hand-waved at best, but still).