The two rules that make a crossword a crossword

A crossword generator is easy to write and hard to write correctly, and the gap between those two is two rules that aren't obvious until you print one out and hand it to somebody.

The easy part takes an afternoon. I know, because it took me one. Take the longest word and lay it across. For each remaining word, look for a letter it shares with something already on the grid and place it at ninety degrees through that letter. Score the candidates — more crossings is better, growing the bounding box less is better — take the best, repeat. The result looks like a crossword.

Then you print it, hand it to somebody, and they get stuck on a row that reads RIVEROTTER.

Rule one: a word may not run straight into another word

The cell immediately before a word's first letter, and the cell immediately after its last, must both be empty.

I assumed I got this for free, on the grounds that every placement in a generator like ours has to cross something, and a crossing is perpendicular. That's wrong, and here's why. RIVER is sitting across, ending at column nine. OTTER comes along, crosses some down word, and the arithmetic puts its first letter at column ten on the same row. Both words are legal. Both cross something. The row now reads RIVEROTTER, and the solver has to work out that it is two answers in a trench coat.

With the rule removed, 77.9% of three thousand generated grids contained at least one run of two or more letters that nobody had written a clue for — 4,197 such runs in total. Real output, not invented examples: RIVEROTTER, PEPPERICED, OTTERSCALA, PEPPERL, REEDH.

Rule two: a letter that isn't a crossing may not touch a neighbour side-on

This is the subtle one, and it's the rule people leave out.

Take OTTER running across. Every one of its five letters has a cell above it and a cell below it. If the cell above the first T happens to be occupied by a letter belonging to some other word, then that column now contains a run of two letters — the T and whatever is sitting on top of it — and that run is not an answer. It isn't numbered. It isn't in the clue list. It is just there, and the solver can't tell it apart from a real entry.

The exception is the entire point of the rule. At a crossing, touching is exactly what's supposed to happen. So the check has two branches, and they are opposites:

• If the cell we're about to write is already occupied, this is a crossing. The letter must match the one that's there, and the perpendicular neighbours are somebody else's problem — they belong to the word we are crossing.
• If the cell is empty, this is a new letter of ours, and both of its perpendicular neighbours must be empty too.

Those two branches are the difference between a crossword and a letter jumble.

With the rule removed, 98.0% of grids contained an unclued run — 19,119 of them across three thousand grids, which is about six per puzzle. The output is a blizzard of two-letter debris: TS, MC, GL, PI, EE. Each one is a place where two answers brushed past each other.

With both rules in place: zero unclued runs in three thousand grids.

Why you don't notice

Because you look at the grid with all the answers in it, and your eye follows the words you intended to put there. The spurious runs are invisible to the person who placed the words and glaring to the person trying to solve them.

Everybody has shipped a bug they were structurally unable to see. This is the cleanest example I have got.

Which is why the check can't live in the generator's head. It has to be a pass over the finished grid: walk every maximal run of two or more letters, across and down, and assert that each one is a word somebody wrote a clue for, that it is numbered, and that it appears in the lists. That single assertion is what separates a crossword from a jumble, and it runs on every build.

The corner you paint yourself into

One more, since you'll hit it about ten minutes after fixing the first two. Greedy placement with a deterministic choice is a disaster: the first few words decide the shape of everything that follows, and the locally best opening move is very often the one that leaves nowhere to go.

We try forty different orderings of the same word list, break near-ties in the scoring at random, and keep whichever grid fits the most words into the smallest bounding box. Forty is not a researched number. It's where the improvement stopped being visible and the tab still felt instant.

And a word that genuinely cannot cross anything — give the generator AAA, BBB and CCC and only one of them can be placed — is reported back as unplaced rather than quietly dropped. Silently losing a word is the other way a puzzle maker lies to you.

What this grid isn't

These two rules make a grid legal. They don't make it good.

A newspaper crossword has properties ours doesn't: rotational symmetry, no unchecked letters (every square belongs to both an across answer and a down answer), a minimum entry length, a single connected block of squares. We enforce none of that. What we produce is the free-form criss-cross grid you'd print for a classroom or a party — every entry crosses at least one other, nothing reads that shouldn't, and the overall shape is whatever the words gave us.

Getting a symmetric, fully-checked grid needs a different algorithm entirely: start from a pattern of black squares and fill it, backtracking when you fail, with a dictionary to fill it from. That is a much larger program, and on a free tool where the words are supplied by the person making the puzzle it would solve a problem nobody brought us. I would quite like to build it anyway.

Local rule, global failure

Both rules here are decisions about a single cell and its immediate neighbours. Both of the failures they prevent are properties of the finished grid that no individual placement is responsible for.

When that's the shape of a problem, you need the rule in two places. Put it where the decision is made, so the generator can't produce the bad thing. Put the proof where the artefact is finished, so you find out when the rule was wrong. Neither one is enough on its own — a generator whose rules you trust but whose output you have never read back is a well-commented guess.

We build Wordmere, a cosy word game where the words you find assemble a small world around you. The companion to this one is the bug that makes word search answer keys wrong, which comes from the same engine and the same lesson. These posts are the things that went wrong on the way.