Crypto Cross dev diary: making crossword puzzles

Our first game Alphabet Connection had auto-generated levels, so we were able to offer level packs with hundreds of levels. No such luck with Crypto Cross: the clues at least have to be written by hand (which is a silly expression by the way; ‘by head’ is nearer the mark than ‘by hand’).

This post is a quick report on the evolution of our level-making process for Crypto Cross: how we went from pen and paper to a custom-built iPad app.

The Naïve Approach

You have to start somewhere, and we started as simply as possible. Zero automation, 100% legwork. At this point I was still fostering notions of old-school puzzle-construction work, toiling away by the flickering light of a tallow candle, etc.

Pen and paper for myself:

cryptocross puzzle on paper

Photoshop for Mansi:

Puzzle designed in Photoshop

Employing the Computer

The slippery slope to automation hell begins when you channel your inner Dennett and perceive the first sub-task that can be automated away.

In my case, I realized a crossword grid can be viewed as a collection of constraints on words, and so finding words for a particular level or puzzle is just a question of choosing ‘good’ words that fit those constraints. So what I need is an English dictionary, a declarative description of constraints and a program to choose from the former and fit into the latter. My Prolog skills being rusty, I had to make do with Python.

So here’s a grid:

grid sample

And here’s how I describe it in Python (a snippet from dictmaker.py):

rules9x9_0 = []
rules9x9_0.append(['a1', 7, {}])
rules9x9_0.append(['d1', 9, {0:('a1',0)}])
rules9x9_0.append(['d2', 5, {0:('a1',6)}])
rules9x9_0.append(['a4', 3, {0:('d1',4)}])
rules9x9_0.append(['a6', 5, {4:('d2',2)}])
rules9x9_0.append(['d5', 5, {0:('a4',2)}])
rules9x9_0.append(['a8', 5, {0:('d5',2)}])
rules9x9_0.append(['a9', 7, {0:('d5',4)}])
rules9x9_0.append(['a10', 3, {0:('d2',4)}])
rules9x9_0.append(['d3', 9, {4:('a10',2), 8:('a9',6)}])
rules9x9_0.append(['d7', 5, {0:('a6',2), 4:('a8',2)}])

Fairly straightforward, each entry holds an index to the start of a word (the orientation, whether across or down, doesn’t matter), the length of the word, and constraints on which letter of this word must equal which letter of a previously constructed word. It is possible to choose a word earlier on that exhausts our choices going down the dependency funnel, but one merely has to begin again with new random choices. So here’ s what a run of dictmaker looks like:

$ python ../dictmaker.py
a10 yom
a1 vizored
d7 endow
a4 add
a6 adept
a9 yashmac
a8 sowed
d5 dishy
d2 dotty
d3 spasmodic
d1 vibrators

This is the dictmaker program. However, it will more-or-less always come up with one or two non-kosher words. They may be too obscure for crosswords, or they may describe body parts, and so forth. I wouldn’t put d1 above in a family puzzle.

So there is also a helper program, called wordhelper, which lists all words in the dictionary that are a given length and have certain letters in certain given positions. So, for instance:

$ python ../wordhelper.py 7 0 i 4 r
icteric icterus ignored ignorer ignores imbarks immerge immerse immoral immured immures imparks imparts imperia imperil imports inburst incurve indorse inearth infarct infares inferno infirms informs inhered inheres inherit injured injurer injures innards innerly innerve inserts insured insurer insures interim interne interns inthral intorts inturns inverse inverts inwards isogram isogriv izzards

wordhelper suggests a list of alternatives and we choose one “by hand.” Inferno is a good word.

The Small Matter of a Good Dictionary

The crossword puzzle experience is very different from playing a game like Scrabble, in which words are merely strings of symbols, and meaning don’t matter. Crossword puzzle words have to be common enough to be in the vocabulary of all players, in Scrabble being in the vocabulary of just one player will suffice. And of course, one has to be able to recall a word given its meaning and a fixed letter or two.

I started with /usr/share/dict/web2 on Mac OS X, Webster’s Second International dictionary from 1934, which may be used to cheat at online Scrabble. I also tried Ross Beresford’s UKACD dictionary, which is freeware. They were OK, but they seemed to lack newer, more interesting words; and they were missing proper nouns, which is the bigger problem.

Where can you get a modern word list that would include proper nouns? Wikipedia 🙂

Taking it with you

At this point I had a nice workflow going, but there were a few improvements that could still be made. (Why be a programmer if you can’t make improvements?)

  1. I had to copy-paste words manually into the puzzle database.
  2. I would often mess up the word->constraints mapping, and specify the wrong constraints to wordhelper (thus getting the wrong words back).
  3. Why can’t I do this from the beach? Or while I’m watching TV? Why have command-line tools when I could have an iPad app?

Enter CCPuzzleMaker, the in-house Crypto Cross puzzle-construction iPad app. The Python code above translates nicely to Objective C with the new NSArray and NSDictionary literal syntax:

NSMutableArray *puzzle9x9_0 = [[NSMutableArray alloc] init];
 [puzzle9x9_0 addObject:@[@"a1", @7, @{}]];
 [puzzle9x9_0 addObject:@[@"d1", @9, @{@0:@[@"a1",@0]}]];
 [puzzle9x9_0 addObject:@[@"d2", @5, @{@0:@[@"a1",@6]}]];
 [puzzle9x9_0 addObject:@[@"a4", @3, @{@0:@[@"d1",@4]}]];
 [puzzle9x9_0 addObject:@[@"a6", @5, @{@4:@[@"d2",@2]}]];
 [puzzle9x9_0 addObject:@[@"d5", @5, @{@0:@[@"a4",@2]}]];
 [puzzle9x9_0 addObject:@[@"a8", @5, @{@0:@[@"d5",@2]}]];
 [puzzle9x9_0 addObject:@[@"a9", @7, @{@0:@[@"d5",@4]}]];
 [puzzle9x9_0 addObject:@[@"a10", @3, @{@0:@[@"d2",@4]}]];
 [puzzle9x9_0 addObject:@[@"d3", @9, @{@4:@[@"a10",@2], @8:@[@"a9",@6]}]];
 [puzzle9x9_0 addObject:@[@"d7", @5, @{@0:@[@"a6",@2], @4:@[@"a8",@2]}]];

The actual algo that finds words to fit those constraints is a mess in Objective C, however. All those objectForKey: and objectAtIndex: messages leave the code too messy to decipher if you haven’t seen the Python version. That’s why I’m moving to RubyMotion any day now.

Here’s what the iPad app looks like:

CCPuzzleMaker

Tap ‘generate puzzle’ and you’re done. Don’t like a word? Tap its particular button on the right edge: that word and every word dependent on that word (and so forth) will be randomly replaced so that the constraints are still satisfied. (In some cases it can’t find a match, so just undo the change and try again.) It even packages the puzzle in the final format (minus the clues) so no chance of making a mistake there.

Just one more thing

The one thing we can’t automate away is writing clues for the encrypted words. But that’s the fun part, you say! You’d be right, except that when you’ve done it a few dozen times it can tend to drag a little. Let’s examine my rough heuristics for devising a clue:

  1. Can you think of something clever right away? If so, you’re done. If not, proceed to 2.
  2. Is the word common? Look it up in the dictionary and find a twist on the definition.
  3. Is the word unusual? Look it up in the dictionary and state the definition in a simplified manner.

That’s probably not how the pros do it, but then I’m not a pro.

So to optimize this process: can you spot the common link? The dictionary lookup. If I could find a dictionary API, I could paste all definitions right into the database (it’s a text file) and simply edit out what I don’t need. Wordnik to the rescue! There’s an iOS API, but I couldn’t get it to work, so I had to use the python API and do this step in post-processing. The python API works well, except that it seems to ignore requests for the canonical form of the word.

Finally, there’s a python script that checks for duplicate words in the database, because I would prefer not to have any words repeat.

All done!

When we started out, it took about 20-30 minutes to make a full level. I find it still takes about 10 minutes after all the automation, but I can browse Hacker News and listen to a podcast while I’m doing it.

The only problem is, I still can’t stop thinking of improvements.

Sign up here to be notified when Crypto Cross launches!