Word search generators print wrong answer keys

A word search is two things, not one. There's a grid of letters, and there's an answer key claiming where each word is hidden. Different code produces each of them, and when the two disagree, the person who gets told they're wrong is a child with a pencil.

Here's how they come to disagree.

The naive generator is almost right

Everyone writes the same one. Sort the words longest first. For each, find every position and direction where it fits without contradicting a letter already on the grid, prefer the positions that overlap something (crossings make a tighter, better-looking puzzle), place it, record where it went. When every word is down, fill the empty cells with random letters. Print the grid, print the key.

That's our generator too, and it is correct right up to the last step, where the random letters get a vote.

Say the puzzle contains CAT, placed across on row four. The key says row four. Three rows down, by pure chance, the filler has produced a C, an A and a T on a diagonal. There are now two CATs in the grid and exactly one of them is in the key. A child circles the other one, checks the answers, and your software tells them they are wrong.

How often? More often than I'd have guessed

We can put a number on this, because the check that prevents it is one loop in our engine and the loop can be switched off. So I switched it off.

Twenty thousand puzzles, eight to fifteen words each, every word three to six letters, all eight directions enabled. 37.1% contained at least one word readable somewhere the answer key did not claim.

I would have said five per cent. Broken down by word length, the picture gets sharper:

• Three letters: 12.7% forged, out of 77,252 placements.
• Four letters: 0.94%, out of 14,037.
• Five and six letters: zero, out of 137,475.

So the whole bug lives in short words, which is precisely why it is so easy to ship. Your test list is OTTER, BADGER, HERON, WILLOW, and you will never once see it. The first person to make an animal puzzle for a five-year-old — CAT, DOG, COW, OWL, FOX — gets a one-in-three chance of a lying answer key.

The arithmetic isn't mysterious once you look at it. A three-letter word needs three cells to line up. A fifteen-by-fifteen grid read in eight directions holds a few thousand three-cell runs, and every one of them is a lottery ticket. Buy enough tickets and eventually you win something you didn't want.

The pretty version is the buggy version

Our filler letters aren't drawn uniformly from A to Z. They're drawn from the letters of the words being hidden.

That is purely a looks decision. A uniform fill scatters J, Q and Z across a grid of farmyard animals and they read as signposts — you can find the hidden words by looking for the patches that are suspiciously boring. Drawing the padding from the puzzle's own letters kills that completely. It's the kind of change you make on a Friday afternoon and feel quite good about.

It also biases every single filler cell towards exactly the letters your target words are made of.

Same twenty thousand puzzles, same seeds, uniform A–Z filler instead: 20.6%. The pretty version is roughly twice as likely to lie. And for longer words it is the difference between never and sometimes — in a separate run restricted to five- and six-letter words, the uniform fill produced not one forgery in twelve thousand puzzles, while the blended fill produced them in about one puzzle in fifty.

That's the part I'd carry away from the whole exercise. A change made entirely for appearance moved a correctness property in the wrong direction, and I can't construct the code review that would have caught it.

Fixing it

After filling, for every word in the key, find every position in the grid where it reads. All eight directions, not just the ones the puzzle is using, because a backwards word is still a word a child can circle. Any hit that isn't the position in the key is a forgery. Take one of its cells that is filler rather than part of a placed word, change the letter, look again.

Repeat until clean, with a bound.

The bound matters more than it looks, because changing a letter to clear one forgery can create another — so this is a loop and not a pass. In practice it settles in a handful of iterations. The guard is there so that a pathological word list can't hang somebody's browser tab.

Run with the repair back on, the same twenty thousand puzzles produce zero forgeries.

The case the repair can't touch

Occasionally a forged copy contains no filler at all. Every one of its cells belongs to a word you deliberately placed, which means two of your own words have spelled a third between them, and there is nothing to change. The repair gives up, the whole layout is discarded, and we lay the puzzle out again from scratch, growing the grid if we have to.

In those twenty thousand puzzles, that escape hatch never fired once. It's insurance, not a workhorse, and if you were trimming code you would be tempted to delete it — I nearly did. The reason it stays is that its absence is not a wrong answer. Its absence is an infinite loop.

What we deliberately don't check

We only check the words in the key. The grid is full of accidental other words — there's a RAT and an ARE and a TEN in very nearly every puzzle we produce — and we don't care, because the key has never claimed them. Nobody circles a word that isn't on the list.

A stricter generator would run a dictionary over the finished grid and refuse any real word anywhere. We decided against that, partly on principle and mostly on weight: the puzzle makers load no dictionary at all, the words come from the person making the puzzle, and pulling a few hundred kilobytes of word list onto a page that never reads it costs about twenty Lighthouse points to solve a problem nobody has.

The narrow failure is the one that matters. The key says a word is here, and it is also there. That is the only case where the software tells a correct person they are wrong.

Where else this hides

Any generator that emits both a thing and a description of that thing has this bug available to it. The grid and the key. The build and the manifest. The migration and the schema dump — that one has bitten me twice.

Two code paths, one claim, and nobody checking that they still agree.

The check is almost always cheaper than the generator that needed it, which is the only reason I'd push this on anybody. Read your own output back, and confirm it says what you said it says. Ours runs on every build, over a fixed set of word lists and forty random ones, and it is the reason this post has numbers in it rather than an apology.

We build Wordmere, a cosy word game where the words you find assemble a small world around you. The same engine lays out our crossword maker, which has a different way of going wrong. These posts are the things that went wrong on the way.