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 what I assumed would be the simplest thing I’ve ever built ended up teaching me about one of the oldest problems in information theory.
The “simple” thing
You get a half-finished crossword grid and a queue of letters to place in the empty spots. 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 curating the best ones.
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 even find a hundred solvable by deduction.
And what was worse, this wasn't an optimization problem. I wasn't going to solve it by fixing 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. At this point I was really doubting myself. 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, that the field of possibilities I’d imagined was really just a maze of dead ends.
The glimmer of hope that kept me going was how similar the boards it threw away were 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
Informed by my training as a programmer I chased it like a bug. Maybe it was flaw in the generator, maybe the dictionary was too thin, maybe one of the stripping passes took away too much. But 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, which is expected. The player 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.
It's kind of like the human equivalent of “B as in Bravo”, 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 if you number the five signals 1 to 5 around the clock any given number can be mistaken for either of its two neighbours. This means sending them one at a time you can only really distinguish at most 2 of the 5 numbers, whichever ones would be more than 1 number apart like 1 and 3 or 2 and 4. If you add a third number into the message you introduce ambiguity since it'll blur into at least one of the other numbers already in use. So one message can hold two pieces of information, so you'd assume two sends is worth 2 × 2 = 4. But Shannon noticed you can actually manage sending five. You do this 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 that is too risky to send 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 messages, 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). I won't really go further into the theory, partly because I'm not a mathematician, and partly because this is all I really needed to unblock me so the dopamine ran out.
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. Crosswords ended up being a perfect canvas for this solution since it was already configured into pairs, each cell has a pair of signals (two crossed words). Although the actual theory goes far beyond simple pairs, this was all I needed to rethink the solution.
The flashlight
So far we've been thinking about this problem 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. So the remaining issue I had to deal with was the highly randomized nature of generating boards. I needed to grow boards in the right direction. 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. If someone knows I am still deeply curious though, please reach out.
So my generator still rolls dice but every roll is now a loaded one. At each step it looks at the confusability graph forming under the board and steers away from any words that would add an edge, meaning a served letter with two possible homes, or two open cells that could take the same tile.
Once I applied this new approach 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
In retrospect I think the title of this post is 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 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, 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 becomes 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.