Information theory · word games
Sometimes the medium and the message have a more complicated relationship than you’d expect. Everyone has had to do the “B as in Bravo” thing at some point, spelling a word down a bad phone line, because B and D and P all turn to the same mush the moment the line frays. The noise and your message just aren’t easy to tell apart.
Filtering signal from noise is a common problem in modern communication. It’s what keeps spacecraft in touch with earth across millions of kilometres. Claude Shannon came up with a version of the medium is the message for much less human applications close to a decade before the term was coined. All of this predates my time on earth and it was fascinating to learn how the intersection of these ideas emerged right in the middle of a small pet project of mine.
I’m not a mathematician, just a software engineer trying to keep my mind sharp and get better at writing Rust. I've been a huge fan of word games, and puzzles in general, so I thought I'd take a stab at making one of my own.
This is the story of how the simplest thing I’ve ever tried to ship ended up balanced on one of the oldest open problems in the field.
The “simple” thing
Here’s the whole game. You get a half-finished crossword grid and a queue of letters waiting to go in. You get one letter at a time, and using mostly deduction, and sometimes head scratching and cheating with a dictionary, you place or "plot" them one at a time until you win... As long as you don't make too many mistakes.
Deduction
For the game to be truly solvable by deduction I figured two things would be needed: a player with a big enough internal vocabulary, and a game that doesn't make you guess. You can't get to a point where multiple words or letters could fit the same open cell. If I were the player in this scenario I'd just uninstall the game on the spot, which wasn't the experience I wanted to create.
I honestly thought that was going to be the easy part. It’s a crossword, so I figured the hard part would be building a good dictionary and picking nice grids. I’d love to go back and warn that version of me...
The wall
The dictionary took months, one of the most tedious tasks I've ever had to do "for fun" in my precious free time. But once it was ready I pointed a little generator I had built at my output folder and ran it. I was expecting some potential hiccups, but was fairly confident once the bugs were sorted out I'd be sitting on mountains of puzzles and spend the rest of the time filtering out the best puzzles.
It made about forty, then it stalled. It kept generating boards and throwing every one away because almost none of them came out deducible. I spent a few late nights rewriting the generator and rethinking the whole approach, and it still never got past a hundred.
I was truly lost at this point. A grid of words from a dictionary of over 10 thousand words is a combinatorial ocean. The space of possible boards is beyond human understanding, but my generator couldn’t find a hundred a person could solve.
And what was worse, this wasn't an optimization problem. I wasn't going to solve it by finding some expensive loop or upgrading my laptop. The generator would go through literal thousands and thousands of grids of words without any deducible ones in sight. Maybe I’d misjudged the whole thing and the game I’d dreamed up couldn’t actually exist. For a few days I genuinely thought the project was dead, with my own generator insisting that the open field I’d imagined was really just a maze of dead ends.
The one thing that kept me going was noticing how little separated the boards it threw away from the ones it kept. Many of the failed boards had only one failed sequence letter, meaning if there had been one or two different words it would have passed. I experimented with backtracking and refilling problematic words, but that was a fool's errand.
serve “T” → 2 legal cells. you’d guess.
serve “T” → 1 legal cell. forced.
It wasn’t a bug
For weeks I chased it like a bug. A flaw in the generator, a dictionary that was too thin, a stripping pass that took away too much. It was none of those.
It was the thing from a bad phone line, an old and famous communication problem. A puzzle is a channel. I’m the sender, the player is on the other end, and when I transmit a letter they have to work out which cell I meant.
Ordinary crosswords are noisy channels, and that’s fine. The solver is usually right, and when they’re not they shrug, backtrack, and fix it. A little confusion there is half the fun. But I was building a game that allows you to use deduction, not guesswork. This meant there couldn't be noise, there couldn't be confusion, there had to be zero errors.
Confusability
Here's how I started to visualize the problem I’d been fumbling toward. Each playable cell on the crossword is a dot, and any time two cells could receive the same letter you draw a line between them, whenever they’re confusable. Mathematicians call that a confusability graph. My goal was to achieve a grid of dots that have no lines between any of them, which would represent an independent set. No confusable pairs, no guesswork.
“B as in Bravo” is the same idea in human form, and by a fun quirk of history the phonetic alphabet it comes from was finalised in 1956, the year Shannon published the problem. So there was more than half a century of math already sitting there, waiting for me. I could tell whether a finished board was deducible, but I still couldn’t build one that way on purpose. To do that I had to understand what the theory actually entailed.
Five beats four
Shannon worked this out decades ago: picture five signals spaced around a clock face, each one close enough to its two neighbours that the line could smear them together. If you send them one at a time, you can only reliably interpret two of them. This is because the noise of the channel would blur messages too close to discern. Two out of five is only 40%, which makes for a really unreliable communication channel.
Now here's the clever bit. Number the five signals 1 to 5 around the clock, where each one can be mistaken for either of its two neighbours. Send them one at a time and you can only really trust two of them — say 1 and 3, far enough apart to never blur together. Any third choice and some pair starts to smear. So one send is worth two, and you'd assume two sends is worth 2 × 2 = 4. But Shannon noticed you can squeeze out five, by sending the signals in pairs and treating each pair as a single message: 11, 23, 35, 42, 54. The trick is that two messages only have to be safely different in one of their two slots. That means a signal too risky to use on its own is more reliable inside a pair, as long as its partner keeps the whole message distinct. One extra message doesn't sound like much, but it snowballs. Over ten sends, one-at-a-time thinking gives you 1,024 safe messages; pairing them up gives 3,125. Every signal you add ends up multiplying your options by about 2.236 instead of 2, and that number is exactly the square root of five (√5 ≈ 2.236).
Back to the board. A deducible puzzle is a set of open cells with no confusable pair among them, and those safe messages on the clock are the same thing: an independent set in the confusability graph. The only difference is scale.
The flashlight
Almost everything written about this math runs in one direction. You’re handed a fixed graph and asked to find the independent set hidden in it, or to work out how big it could be. That’s a detector, and a better detector didn’t help me, because my generator was still making boards blindly and tossing nearly all of them. I didn’t need to find an independent set inside a board I was stuck with. I needed to grow one. I wanted to build the board so its open cells were an independent set from the very first letter. Initially I chased the dream of a purely deterministic generator that would build a deducible board from the very start, but I quickly realized I was not a strong enough computer scientist to pull that off, if it was even possible.
So the generator still rolls dice but now every roll is loaded. At each step it looks at the confusability graph forming under the board and steers away from any move that would add an edge, meaning a served letter with two possible homes, or two open cells that could take the same tile. It uncovers the one square that breaks a tie, prefers the fill that leaves the fewest confusable pairs, and gives up on any branch it can’t save. Shannon’s structure went from a test I ran at the end to the thing steering the build from the first move.
Once I applied it the boards finally came in the thousands. There are still tight spots where I have to raise the retry limit, loosen a timeout, or reseed it, but it runs reliably enough that there’s now a library of more than 9,000 playable puzzles lined up, roughly ten years of dailies.
The number, re-seen
I had the title of all this backwards. The number nobody knows isn’t some far-off constant at the frontier of math. It’s right here on every board, in miniature. Every move is a tiny question with a single numbered answer: which cell does this letter go in? Almost always the surrounding words pin it down and you answer without thinking. But without that insight from Shannon I would have ended up with two cells both fitting the same letter, both spelling real words, and now there are two answers with nothing on the board to tell them apart. For that moment the right cell would genuinely be unknowable. A number, or letter, nobody knows. The solution to this in the end, as it is in many cases, is to add context. Uncover one more tile, fill in one more crossing word, and the unknowable collapses back to a single unambiguous choice.
Alfred North Whitehead once said, “Seek simplicity and distrust it,” a lesson I seem destined to relearn countless times. You, on the other hand, get to trust it completely: a letter, a cell, and never once a guess.
It’s a real game, Motplot. Give it a try if you’re interested.