How to generate an arrowword with a hidden message

You can generate a Swedish-style crossword (arrowword) with a hidden message in two phases. First use a local search to find the mask, that is, the layout of clue cells and letter cells, and then fill it with dictionary words as a constraint satisfaction problem (CSP) solved with backtracking. Do not place the hidden message in advance. Only once the crossword is finished, look for a joke whose punchline can be read in it from left to right and top to bottom.

This is how the arrowwords in our crosswords and word search app (App Store, Google Play) are made. One grid takes from a few seconds to tens of seconds of CPU time, so we generate them in advance on a more powerful computer and bundle them with the app. Word searches are generated in a completely different and simpler way, described in How to generate a word search with a hidden message.

#What an arrowword has to satisfy

An arrowword has no black squares. Every cell is either a letter or a clue with an arrow pointing right or down. That gives a set of hard constraints:

• Every letter belongs to both an across and a down word. A letter crossed by only one word cannot be checked and looks like a mistake.
• Every word has at least two letters and a clue in front of it. That is why the first row and the first column are always all clues.
• The letters form one connected area, with no detached islands.
• Every word must be in the dictionary and have at least one clue. No word appears twice in a grid.

On top of that come soft quality criteria: few two-letter words, no clues that point at nothing, and as few very long words as possible, because they are hard to fill. The problem is computationally hard. Engel et al. (2012) showed that filling a mask with words is NP-complete on its own.

#Why filling the grid word by word is not enough

The first idea is to do what a person with a pencil would do: split the hidden message into words, lay them out in a row like in a newspaper, run a crossing word through each of its letters and fill the rest of the grid with a greedy algorithm. A greedy algorithm picks whatever looks best at each step and never revisits the decision. Where nothing fits, a hole remains. And because greedy filling cannot go back, once the first ten words are bad, the rest of the grid cannot fix them.

A better word selection heuristic helps only a little. You can try crossing word lengths from medium, around five letters, towards the extremes. Or you can go evolutionary: a population of partial crosswords, five children per parent with one more word each, a score based on filled cells, vowel count and how evenly the letters are spread, and only the best move on to the next generation. The results get somewhat denser, but the holes stay, because the heuristic only sees the next step.

The way out comes from Jakob Engel's bachelor thesis at TU Munich (2009); he is also the first author of the paper above. Split the task into two independent phases: first find a good mask without caring about words, then fill it. Engel used an evolutionary algorithm for the mask. We use a simpler local search with random shakes, described in the next step.

#Step 1: the mask with hill climbing

The mask is a grid in which every cell is either a clue or a letter. Hill climbing is enough to find one: a local search that makes small changes and keeps those that do not make the result worse.

Start at random, with clues on about 22% of the inner cells. Give every mask a penalty score. Hard violations (a word that is too short, a letter without a crossing word, a detached island) should mostly cost 1,000 points; soft flaws (two-letter words over budget, a clue that points at no word, clusters of clues) 50 to 500.

Then, in a loop, flip one cell from clue to letter or back, or move a clue one cell diagonally. Keep the change if the penalty did not go up, otherwise revert it. Aim half of the changes at the cells with the highest penalty, and the gross errors disappear quickly:

Hill climbing gets stuck in local minima easily. When 2,000 steps bring no improvement, "shake" the grid: flip five random cells of the best mask found so far and keep searching. Those are the spikes in the chart. If even three shakes bring no better mask and it has no hard violations, stop.

The final mask has a residual penalty of 200 for soft flaws, but no hard violation:

It pays to have the penalties for a clue without a word and for a detached island in the mask from the start. On a large set of finished crosswords without them, 13.2% of clues pointed at no word and 23.5% of grids had a detached island of letters. With them, the figures are 5.0% and 0%.

#Step 2: filling with words as a CSP

The mask yields a list of slots, places for words with a known length and known crossings. Filling them is a classic constraint satisfaction problem (CSP): every slot is a variable, its domain is the set of words that fit, and the constraints are matching letters at the crossings. It is solved with backtracking, a search that steps back and tries another option whenever it hits a dead branch:

for every slot: domain = all words of that length
while not all slots are filled:
    pick the slot with the smallest domain (on a tie, the one with most crossings)
    for every word in its domain, best first:
        place the word
        narrow the domains of crossing slots to words with the matching letter
        if any domain became empty: undo, try the next word
        otherwise continue with the next slot
    if no word fits: go back one slot
give up after 50,000 steps

In the literature these heuristics are called MRV (minimum remaining values, the slot with the fewest options first) and forward checking (narrow the neighbours' domains after every placement, so a dead branch shows up immediately, not ten words later). Pre-index the dictionary by length, position and letter. "Words with Q in third place" is then a single set intersection, not a scan of the whole dictionary.

Word order matters too. Put words with more distinct clues in the dictionary first. It is a simple signal of a common crossword word. Without it, the grid fills up with obscure abbreviations.

#Step 3: the hidden message in the finished grid

While filling, you do not know the hidden message yet. Read the letters of the finished grid from left to right and top to bottom and look for a joke whose punchline is a subsequence of that string. The letters come in the right order, but they do not have to be adjacent. If one is found, spread its letters as evenly as possible across the grid, so the punchline cannot be guessed from a single word.

This order (grid first, joke second) increases the number of finished crosswords dramatically. In our measurement a single 12×12 grid fits on average 86 jokes from the Slovak list (5,960 jokes). So there is always one that has not been used in that size yet.

#Why not place the message in advance like newspapers do

In newspapers the hidden message is usually in one place, in a row, split into words. There are two ways to get that, and both give very few results.

The first is to place the message in the grid in advance. Then it has to fit. Our punchlines have 10.3 letters and 2 words on average. This is the share of jokes from the Slovak list that can be placed in a given size at all:

With the message placed in advance, filling small grids succeeds about as often as without it. For 15×15 it was 5 out of 60 attempts versus 8 without it, for 18×18 none out of 60. Each such grid also serves a single joke, and in small sizes most jokes cannot even be placed.

The second way is to let the grid form freely and look for the punchline in it as a contiguous run. In a sample of 2,200 finished Slovak crosswords (200 of each size from 8×8 to 18×18), the whole punchline appeared as a contiguous run in one row or column in only 81 grids (3.7%). When each word of the punchline may sit somewhere else, it is 443 grids (20%), still without requiring the words to be next to each other. Reading in order found a joke in every one of them. At the price of a hidden message scattered across the grid you get orders of magnitude more crosswords.

#Generator performance and why it does not run on the phone

The generator ran 60 attempts per size with the Slovak dictionary, single-threaded (JavaScript on Node 22, an Intel Xeon 2.8 GHz server CPU in the cloud). An attempt is one mask and one fill. "Successful fill" means the CSP found a solution within 50,000 steps.

What the numbers show:

• A small grid is not an easy one. An 8×8 grid has many short slots with many crossings and little freedom; filling succeeds in only 5% of attempts. One filled grid costs on average about 10 seconds of CPU time at 8×8, 4 seconds at 12×12 and 18 seconds at 18×18.
• Most attempts fail. So run attempts in parallel on all cores and take the first result that is good enough.
• It makes no sense on the phone. Players do not want to wait tens of seconds when they open a puzzle, and the app would have to ship the whole dictionary with clues. A generator inside the app also has to keep yielding to the UI, otherwise the app freezes.

#Generating at scale

The generator therefore belongs on a computer with a multi-core CPU. In our setup each core gets its own thread with the dictionary loaded once at startup. A grid is done when one of the threads returns a result with few enough unused cells. In continuous mode it keeps generating one crossword of every size in every language. That is how we got over 14,000 crosswords in four languages (Slovak, Czech, English, German) and eleven sizes from 8×8 to 18×18. Each joke is used at most once per size and language.

At this volume two things matter:

• Format. A full record takes about 28 kB per crossword and 390 MB for the whole corpus. Most of it can be derived (coordinates, cell types, clue numbers). A compact format with the grid stored as a single string takes about 2 kB, 15 MB for the corpus and about 7 MB in the app's install package.
• Measuring quality. Measure the share of clues without a word and of grids with islands after every generation, and let the check fail if the numbers get worse.

#What the approach does not cover

• Clues without words. The average crossword still has 2.7 clues that point at nothing. The top left corner is always one of them.
• Dictionaries without frequencies. The German dictionary from Wiktionary has a single clue for most words, so ranking by clue count barely discriminates and rare words end up in the grid. A frequency list would help; we do not have one yet.
• The hidden message is not in one place. People used to newspapers may look for it in a row. It is a compromise, not the ideal.

If you are working on a similar content generation problem or need a mobile app, get in touch.