How Anagram Solvers Work Without Checking Every Permutation

The obvious way to solve an anagram is to try every arrangement of the letters and check each one against a dictionary.

For seven letters that is 5,040 arrangements, which a computer does instantly. For ten letters it is 3.6 million. For twelve it is 479 million. The obvious method falls apart exactly when you most need help.

Real solvers never generate a permutation at all.

Invert the problem

The insight is to preprocess the dictionary rather than the input.

Take every word and sort its letters alphabetically. “Listen” becomes “eilnst”. So does “silent”, “enlist”, “tinsel” and “inlets”. They collapse to the same key, because that is what being an anagram means.

Store the dictionary as a map from that sorted key to the list of words sharing it. Now, to find anagrams of an input, sort the input’s letters and do a single lookup.

The cost of finding all anagrams of a twelve-letter word drops from 479 million operations to sorting twelve characters and reading one entry from a map. The sorting step is what mathematicians call a canonical form: a way of writing something so that all equivalent things look identical.

Finding shorter words

Full anagrams are only part of what you want. Given seven tiles, you mostly want every word that uses some of them.

Sorted keys do not help here, because “eilnst” tells you nothing about “list” or “ten”.

The right structure is a letter count. Represent each word as a 26-slot tally: how many As, how many Bs, and so on. Do the same for your input.

A word is playable if, for every letter, its count never exceeds yours.

rack:  a=1 e=1 i=1 l=1 n=1 s=1 t=1
"list": i=1 l=1 s=1 t=1    every count fits    playable
"less": e=1 l=1 s=2        needs 2 s, you have 1    not playable

That is one comparison per dictionary word, and it does not care at all how many letters you typed. A pass over a few thousand words is instantaneous, which is why a good solver responds as you type.

Wildcards

A blank tile stands for any letter, and the count method extends to it neatly.

Instead of requiring every letter to fit, add up the shortfalls. If a word needs two more Ss than you have and one more E, that is a total shortfall of three, and the word is playable if you hold at least three blanks.

The cost is that each wildcard multiplies the search space, so two is a sensible limit for an interactive tool. Beyond that you are matching against most of the dictionary anyway, and the answer stops being useful.

The dictionary is the hard part

The algorithm is straightforward. Choosing the word list is where solvers actually differ, and where most of them go wrong.

The tempting move is to grab the largest available public word file. On most Unix systems that is /usr/share/dict/words, derived from a 1913 edition of Webster’s. It has about 235,000 entries, which sounds excellent.

It is a bad choice for two separate reasons.

It contains enormous amounts of obsolete vocabulary. “Favism”. “Biga”. “Uncurse”. “Rightle”. Searching seven letters against it returns pages of words nobody has used in a century, and the one you wanted is buried on the third screen.

It is missing ordinary words. Because it is a list of dictionary headwords rather than word forms, it largely excludes inflections. It does not contain “books”, “runs”, “houses” or “walked”. It does contain “graving”.

So the file is simultaneously far too large and missing the plurals you were looking for, which is a genuinely impressive combination.

The better approach is to build up rather than filter down: start from a curated list of common base words, apply regular English morphology to generate the inflected forms, and gate the verb inflections so that nouns do not sprout past tenses. Smaller, and every entry is a word a person would recognise.

Word lists have jurisdictions

There is no single correct English word list, which surprises people who expect a solver to be authoritative.

Competitive Scrabble uses different lists in different regions. North American tournaments use one; most of the rest of the world uses a larger list that includes many British and Commonwealth words. Words valid in one are invalid in the other, and this is a settled fact rather than a dispute.

Crossword setters, meanwhile, work to a completely different standard, drawing on proper nouns, phrases and abbreviations that no game list would accept.

So a solver can only ever tell you whether a word is in its dictionary. Treating a miss as proof that something is not a word is a category error.

The oldest use of anagrams

Before they were a game, anagrams were a serious tool for establishing priority.

In 1610 Galileo announced his observation of what turned out to be Saturn’s rings as a Latin anagram. This let him timestamp the discovery publicly without revealing it, buying time to confirm the observation before a competitor could claim it. Robert Hooke did the same in 1660 with his law of elasticity, publishing “ceiiinosssttuv” and revealing two years later that it unscrambled to “ut tensio, sic vis”.

It is a cryptographic commitment scheme built out of the alphabet: publish something that proves what you knew, without disclosing what you knew. The seventeenth century arrived at the same idea as a modern hash commitment, using nothing but rearranged letters.

Which is a considerably better pedigree than most word games can claim.