Crossword Puzzle Construction

Closing in on the end of the section, this is a “private communication” problem that I think I figured out myself.

The problem: Crossword Puzzle Construction.  This is problem GP14 in the appendix.

The description: Given a set W of words (strings over some finite alphabet Σ), and an n x n matrix A, where each element is 0 (or “clear”) or 1 (or “filled”).  Can we fill the 0’s of A with the words in W?  Words can be horizontal or vertical, and can cross just like crossword puzzles do, but each maximally contiguous horizontal or vertical segment of the puzzle has to form a word.

Example: Here’s a small grid.  *’s are 1, dashes are 0:

* *
 –  –  –
 –
* * *
* * * *

Suppose our words were: {SEW, BEGIN, EAGLE, S, OLD, SEA, EGGO, WILLS, BE, SEA, NED}.  (Notice the lone “S” is a word.  That’s different from what you’d see in a normal crossword puzzle)

We can fill the puzzle as follows:

* S E W *
B E G I N
E A G L E
* * O L D
* * * S *

Notice that we can’t use the first two letters of “BEGIN” as our “BE”, because the word continues along.  That’s what the “maximally contiguous” part of the definition is saying.

Reduction: From X3C. We’re given a set X with 3q elements, and a collection C of 3-element subsets of X.  We’re going to build a 3q x q puzzle with no black squares. (We’ll get back to making this a square in a minute)  Each word in W will be a bitvectorof length 3q, with a 0 in each position that does not have an element, and a 1 in the positions that do.  So, if X was {1,2,3,4,5,6,7,8,9} the set {1,3,5} would be 101010000

We also add to A the 3q bitvectors that have exactly one 1 (and 0’s everywhere else). The goal is to find a subset of C across the “rows” of the puzzle, such that the “columns” of the puzzle form one of the bitvectors.  If we can form each of the bitvectors, we have found a solution to X3C.  If we have a solution to X3C, we can use the elements in C’ and place them in the rows of the 3q x q puzzle block to come up with a legal crossword puzzle.

We’re left with 2 additional problems:  The grid needs to be a square, instead of a 3q x q rectangle, and the legal crossword puzzle solution needs to use all of the words in W, not the the ones that give us a C’.  We can solve both by padding the grid with blank squares.  Spaced out through the blank spaces are 1 x 3q sections of empty space surrounded by black squares.  We can put any word in C-C’ in any of these sections, and that’s where we’ll put the words that are not used.

(This also means we’ll have to add 3x|(C’-C)| 1’s and (3q-3)|(C’-C)| 0’s to our word list for all of the 1-length words in those  columns.)  Then we add enough blank spaces around the grid to make it a square.

Difficulty: 5 if I’m right, mainly because of the extra work you have to do at the end.  The comments in G&J say that the problem is NP-Complete “even if all entries in A are 0”, which is usually a hint that the “actual” reduction used an empty square grid.  I wonder if that reduction doesn’t have my hacky stuff at the end.

Leave a Reply

Your email address will not be published. Required fields are marked *