We implement an algorithm to build a crossword array for a set of given words based on hashing techniques.

In Chapter 6 of my Mathematica GuideBook for Programming, as an example of list manipulations, I discuss how to build a crossword array. While this serves as a good example for more advanced list manipulations, using lists is not the optimal way to build crossword arrays. The complexity of adding a new word to words already placed using the list-based method is , so that the total complexity of constructing a crossword array with words becomes .

Over the last few years, some Mathematica users have asked me if it would be possible to build crossword arrays faster. The answer is yes. If we use hashing techniques, we can quickly and in constant time check if a given lattice element is available and can therefore reduce the overall complexity from to , which for thousands of words makes a large difference in computation time. Such a method is implemented in this column. When placing the individual letters of a word on a square grid, various cases have to be considered. As a result, this column contains a larger-than-normal amount of procedural code. Some of the function definitions are a bit longer, but with the comments between the computation steps and decision paths, the code should be easily readable.

To be self-contained here, we do not require any material from the GuideBook implementation.

Here is the formulation of the problem:
Suppose we are given a list of words as strings. The aim is to insert them in a rectangular grid of squares in such a way that each word is either horizontal (reading from left to right) or vertical (reading from top to bottom), and such that words are connected at squares containing a common letter. Here is an example that uses words of high relevance in the German state of Thuringia, some cultural, and some of culinary value. (In the rest of the column, we use more Mathematica-related words as examples.)

For better readability, we require that any two horizontal words and any two vertical words be separated by at least one blank square. In addition, no horizontal word should begin or end in a square that is next to one occupied by a letter in a vertical word, and similarly no vertical word should begin or end in a square that is next to one occupied by a letter in a horizontal word. (Equivalently said, these squares must be blank: those immediately to the left and right of a horizontal word and those immediately above and below a vertical word.) However, we do allow a word to begin or end in a square occupied by another word.

We position all words on a square grid (not limited in size) built from individual squares and keep track of the content of each square.

The function positions the list of characters characterList so that the element of this list is positioned at the square and the word characterList is aligned (either horizontally or vertically, indicated by "" or "" , respectively. We use to indicate the current status of a square. The following are possible:

• —This square must stay empty.
• —This square contains character char and is part of a horizontal and a vertical word.
• —This square contains character char in a vertical word and could still be used in a horizontal word.
• —This square contains character char and could still be used in a vertical word.
• —This square contains no character yet and could be used in a horizontal word.
• —This square contains no character yet and could be used in a vertical word.

All such information is associated with the down values of the function status; gives the current state of the square centered at . It either returns or stays unevaluated in case the square has not yet been used in any way and does not neighbor any already positioned word.

We associate a function value for the current content of a square using . This allows for a constant-time lookup of the status of each square needed using .

The function positionAWord sets the values of the squares where the characters of a word are placed and also adds information about the potential later use of the neighboring squares. For instance, the squares immediately above or below a horizontally placed word can only be used later for vertical words.

The optional last argument of positionAWord allows for potential side effects, like monitoring the order of attaching the words, which we use below. The various cases to be considered are easily seen in the comments of the following code.

As an example, we position the word Mathematica at the square horizontally.

And these are the current squares that are marked.

To see the progress of the construction visually, we define a function makeCWPGridGraphics that colors the squares according to their current status.

The following graphic visualizes the current status of the squares near the placed characters.

The function checks if it is possible to position the list of characters characterList so that the element of this list is positioned at and the word is aligned either horizontally or vertically, indicated by “” or ““, respectively. To do this we must check that each of the needed squares is either available or already has the needed character in place. And the neighboring squares must be empty or have letters from an already orthogonally positioned word. The auxiliary function whileTrueLoops is an iterating function that stops iterating when the first incompatible square is found by using the mechanism. In the following, we always assume that a new word is only placed using the function positionAWord in case positioningAWordIsPossibleQ gives True.

With the already placed horizontal word Mathematica, we can position another copy of Mathematica vertically.

But, we cannot place another horizontal Mathematica at the same position.

Nor can we place another copy along the already placed word starting in the middle.

Of course, we could also position another copy of Mathematica in the middle, say at the first “m” of the horizontal Mathematica.

This gives the following state of our grid.

The function finds a possible placement for the characters of the word characterList and places those characters. The function either returns the coordinates of the placement of the attachment character or returns $Failed in case no possible attachment is found. We also give this function a few self-explanatory options that, among others, allow the placement of the new words to be as central as possible or as far apart as possible. The option setting Inner tries to attach the next word inside the given words, the setting Outer tries to attach the next word at the outside of the given words, and the option setting RandomSample chooses a random position for the next attachment.

Finally, we define the function which constructs the actual grid of letters from the down values of status.

The following graphic shows the state of all already touched squares after attaching the word Mathematica six times to the initial word Mathematica. The gray squares contain already placed words, the red squares must stay empty, and the green squares allow further words to be attached. The arrows indicate in which direction potential words can be attached.

The following graphic shows some steps in the process of building the crossword arrays. Looking in detail at the values of the squares makes it easy to understand the details of the above-implemented algorithm.

Using the function Manipulate, we can easily construct an interactive version that lets us see all the steps of the growth process. The following interactive version lets us monitor the growth for the first twelve steps.

Now let us analyze the complexity of the approach implemented. Because the lookup of the current state of a square is approximately constant (independent of the number of already set squares), we expect a linear complexity in the number of words. As a test, we place the word Mathematica 500 times. To visually follow the progress, we use Monitor.

Next, we display the measured timings. The right graphic shows the cumulative average time needed to attach a word. It increases linearly with the number of the word to be attached.

And the cumulative time to form a crossword array of words has complexity . The following graphic together with a fit shows this clearly.

This is the resulting crossword array. We use a small font to display it in its entirety.

Because of the much better runtime of this caching-based approach for a larger numbers of words (say thousands), we can now quickly position the first 250 words by using a built-in function in a crossword array.

The following graphic shows the order in which the words were placed in the plane. Red, tall towers indicate words that were positioned early, and blue, low towers indicate later ones.

And here is a crossword array of all the visualization functions and their options.

We continue by using the potential function in positionAWord. We use the function to record to which positioned word a character belongs.

By implementing a small variation of the function makeCWPGrid, we can now use the information associated with to color the positioned words.

This results in the following colored grid elements. At the crossings, we blend the colors.

We end with a function CrossWordConstructionCached that tries to position a list of words into one crossword array.

Here are two ways to position all the three-digit primes in such an array.

References

M. Trott, “Constructing Crossword Arrays Faster,” The Mathematica Journal, 2011. dx.doi.org/doi:10.3888/tmj.11.2-1.

About the Author

Michael Trott
Senior Member, Technical Staff
Wolfram Research, Inc.
mtrott@wolfram.com