How an Anagram Solver Works (and Why It's Instant)
By Mir Hadi ·
Type LISTEN into an anagram solver and SILENT, ENLIST, TINSEL and INLETS come back before you lift your finger. The speed comes from one small idea: the solver sorts your letters into alphabetical order and looks that sorted key up in a dictionary that was sorted the same way in advance, so it never tries every arrangement.
Why is brute force hopeless?
Six different letters can be arranged in 720 orders, which is 6 factorial. Seven letters: 5,040. Ten letters: 3.6 million. Checking each arrangement against a dictionary works for short words and falls over quickly after that. And it’s the wrong shape of problem: we don’t want every arrangement, we want the few that are words.
How does sorting the letters find anagrams?
Two words are anagrams of each other exactly when they contain the same letters. Sort the letters of each word alphabetically and anagrams become identical strings: LISTEN, SILENT, ENLIST and TINSEL all become EILNST.
So the solver sorts every dictionary word once, ahead of time, and files words under their sorted key. When you type LISTEN, it sorts your letters (EILNST), looks up that one key, and reads off the list. One lookup instead of 720 checks. Ten-letter inputs cost the same as six-letter ones.
Shorter words inside your letters
The second thing a solver shows is every shorter word you can make: LIST, TILE, NEST and so on. That’s a different question. For each dictionary word, can it be spelled from your letters? The solver counts how many of each letter you have, counts what the candidate word needs, and checks that you have enough of each. A blank tile is a letter you’ll allow to be anything, so it covers one shortfall. In Scrabble the shortest results earn their keep too: two-letter words are what let you play parallel to a word already on the board.
That check is cheap, and the solver can skip most words before counting anything: if a word contains a letter you don’t have at all, it’s out. With a little bookkeeping (a 26-bit “which letters are present” mask per word), filtering 168,000 words takes a few milliseconds.
Why results come in a particular order
Longest first, because in most games longer words score more. Within a length, common words first, because when you’re solving a puzzle the answer is far more likely to be TINSEL than ELINTS. The frequency ranking comes from how often each word appears in real text.
What it can’t do
A solver only knows the words in its list. Ours is built from ENABLE, the open list most word games use, plus additions. Proper nouns aren’t in it, so names won’t solve; and tournament Scrabble lists differ by a few hundred words, so a disputed word should be checked against the official dictionary.