2022-01-26 (last updated 2022-11-17)
Almost all mathematical questions one could have about Wordle aresettled by now. I summarize here what is known sofar.
tl;dr
- If we exploit the 2309-words solution list:
- Wordle canbe solved in 3.4201 guesses on average, with 5 guesses at worst(i.e., 100% of the time comfortably within the allowed 6 guesses).
- The corresponding decision tree is optimal both in terms ofaverage, and in the worst case: It wasproven that it is not possible to get an average lower than 3.4201,nor is it possible to have a worst case of 4 guesses, evenindependently.
- In hard mode, Wordle canbe solved in 3.5076 guesses on average (with 6 guesses at worst,i.e.100% of the time). Or, with a different decision tree, itcan be solved with a slightly worse average, but alwayswithin 5 guesses. Again, both trees are optimal for theirrespective objective functions.
- Instead of using a decision tree, we can also consider the problemof solving the game starting with a fixed set of guesses independent of the game’s answers. This can be donewith 7total guesses (6 fixed guesses plus the winning guess), even if we onlyallow guess words from the 2309-words solution list. This result isoptimal: it is impossible to play 5 fixedguesses, then always win Wordle with the sixth.
- For the full 12972-words dictionary:
- Wordle can be solved in 6 guesses at worst(i.e.100% of the time just within the allowed 6 guesses), with4.07771 guesses on average.
- In terms of the worst case, the above result is optimal: Itwasproven that it is not possible to find a decision tree whose worstcase is 5 guesses or less.
- In terms of the average, 4.07771 is not proven optimal, but there isstrongevidence suggesting that it probably is.
- In hard mode, Wordle can be solvedin 7 guesses worst, 4.52629 guesses on average. The worst case isoptimal: Hard mode Wordle cannot be solved 100% of the timewithin 6 guesses. Moreover, the 4.52629 average cannot be improved whilemaintaining the 7-guesses worst case.
- Alternatively, we can play 10 fixedguesses, then always win with the 11th. This is optimal.
- In terms of computational complexity:
- If we abstract away thedictionary and the alphabet (our input), finding an optimal strategy isNP-hard.
- However, if we fix the alphabet size, it can be done in polynomialtime.
Note that the New York Times bought Wordle and tweaked the word listsontwo occasions. Ultimately (since 2022-03-16), their changes amountto removing 6 words from the original solution list (now 2309 words),while retaining them as allowed guess words. The results above wereupdated for the latest word lists.
Update 2022-08-20: The NYT has added two words tothe list of allowed words. While this should have limited impact on theresults below, none of them have been updated for the change.
Game setup
First, let’s clarify a few things about the game:
Wordle comes with a dictionary of 12972 words that the player isallowed to use as guesses. They are essentially all 5-lettercombinations one could reasonably argue are English words. The “secret”word that the player has to discover is also always in thatdictionary.
It is so trivially easy to cheat at Wordle that there is no point toit: The list of secret words is right there in the code of the game. Thedaily secret words are picked sequentially from that list, so they areall known since 2021-06-19 (“cigar”) and until
2027-10-202027-10-14, for a total of23152309 scheduled secretwords.One could always look up that list for the current date and solve thegame immediately at the first guess. However, this is not much fun(mathematically), so we need to define the game somehow. There are twoobvious options:
“Full dictionary”: we consider that the secretword could be any word from the full 12972-word list.
“Solution list”: we know that not every word canbe a secret word, and take advantage of the knowledge of the list of2309 scheduled secret word (but we ignore its order, which wouldtrivially allow us to win every game in one guess).
While many focused on finding the best “first word” to play as aguess, the first guess is just a tiny part of what we really want: Adecision tree. A decision tree not only tells you whichguess to play first, but accompaniesyou as you play, telling you which guesses to play subsequentlyin function of the information given you by the game as youplay (i.e.all the letter colors 🟩🟨⬜ so far). I only cover herefixed/deterministic decision trees, which will always reach a givensecret word in the same way, because it is straightforward to giveformal evaluations of how good they are. I will also briefly touch onapproaches to solve the game without decision trees, with a fixed set of guesses.
The word optimal has taken quite a maulinglately in Wordle-related writings. Just to be to be absolutely clear, asolution is optimal only if no better solution can possibly exist. Inparticular, there is no such thing as a “more optimal”solution.
Now, regarding what we optimize, there are two naturalchoices:
The worst-case number of guesses. That is, givena decision tree, what is the maximum number of guesses necessary tocorrectly guess any secret word? In other words, after how many guessesdoes the decision tree guarantee that we win the game?
The average number of guesses. What is theaverage, over all possible secret words, of the number of guesses adecision tree will take to get a win?
As we will see, those are competing objectives, sometimesirreconcilably, sometimes not so.
Buried in the options, Wordle features a hardmode. The game is different in hard mode, in that only wordsthat satisfy the hints given earlier are allowed as player guesses. (Forexample, if a letter is colored green 🟩 after one guess, that lettermust be present in the same position in all subsequent guesses.)
There are subtleties about the rules regarding words with repeatedletters, and this particularly affects hard mode. However, it seems thatby now everyone agrees whatthe rules are.
Solution list: 2309possible secret words
In this section, we assume that we know the list of 2309 scheduledsecret words, but we ignore the list’s order (it would be trivially easyotherwise).
For the original word list, CyrusFreshman set up a nice automated leader board with astandardizedinput format. There, we can directly find that fourteen distinctpeople have found decision trees that solve Wordle in 3.4212 averageguesses and (simultaneously) 5 worst-case guesses (i.e., 100% of thetime, never even using the 6th guess), including JonathanOlson, PeterTseng and AlexSelby. With the updated word list, we get anaverage of 3.4201 guesses, still with 5 guesses in the worstcase.
While I suspect all employed similar general approaches (recursiveenumeration / backtracking with tree pruning and some form of caching),I will now mainly defer to AlexSelby’s nicewriteup, because it is the most thorough and because thecorresponding code can answer more of our questions. Alex and Peter bothimplemented their algorithms in such a way that not only they get gooddecision trees, but they can also subsequently perform an acceleratedcomplete enumeration and prove optimality (no tree has anaverage of less than 3.4212, and no tree wins all games in 4 guesses atmost). Alex indicates that the latter is by far the most difficult partcomputationally: finding good trees (that happen to be optimal) isquick, proving that they are indeed optimal is much more expensive.
For hard mode, both Alex and Peter found a decision tree with in3.5085 guesses on average and 6 guesses at worst (i.e., 100% wins in 6guesses), with the original word list. Hard mode is interesting in that,if we are willing to sacrifice a bit on the average, we can improve theworst case: Alex found a different decision tree with 3.5448 guesses onaverage, but a worst case of 5 guesses! Again, Alex reports optimalityon both fronts. With the updated word list, the average becomes 3.5076with a worst case of 6, while againa worst case of 5 is possible.
Full dictionary:12972 possible secret words
In this section, we assume that the game can pick secret words fromits whole 12972-word dictionary. The number of potential secret words isnow about 5.6x as large as in the previous case, dramatically increasingthe size of an already large enumeration space.
Still, the same type of emumeration / backtracking tricks work evenin this case, and with a careful implementation I found a decision tree with 6 guesses in the worst case.Even with the full dictionary of 12972 possible secret words, it is thusstill possible to win every Wordle game within the 6 allowed guesses! Idid not try to optimize for the average number of guesses, but it canstill be measured: 4.2308 guesses on average over the 12972 words. I wasnot able to perform complete enumeration for 5 guesses, so there was nooptimality guarantee. However, complete enumeration did rule out theexistence of trees with 4 guesses in the worst case, leaving afrustrating gap between 4 and 6.
The frustration was short-lived, fortunately, as AlexPeattie proved that it is impossible to build a decision tree with 5guesses in the worst case, making the result sharp. The proofis much more interesting than complete enumeration: it relies oncleverly finding provably-difficult-to-disambiguate word subsets and itcan be checked directly by inspection without any computational tools(although Alex did double-check it with OR-Tools’constraint programming solver).
Thanks of Alex’s proof, we now have an optimality guarantee in termsof the worst case at 6 guesses. It is still an open question whether wecan find a decision tree that is optimal in terms of itsaverage number of guesses.
Update 2022-02-06 MarkFisher found a different decision tree with 6 guesses in the worstcase. His approach is much less brute-force than mine and as a result hehas niceinsights about which words are difficult to disambiguate, and how totackle such word groups.
Update 2022-04-08 Alex Selby improved his code (bytwo orders of magnitude!) and applied it to the full dictionary as well.This let him find atree that solves wordle in 4.07771 average guesses (6 in the worstcase). While there is no proof that 4.07771 is optimal, there is a goodargument to be made that it probably is: Alex managed to show that if wefix the first guess word, this tree is the best one in terms of averagenumber of guesses. Furthermore, this first guess word was deemed themost promising one, far ahead of the others, by a heuristic method(incomplete search) that reliably gave optimal trees in other cases.
For hard mode, Alex found atree that solves wordle in 7 guesses in the worst case and proved bycomplete enumeration that 6 worst-case guesses is impossible! To giveyou an idea of the achievement here, my own code could only find atree with 14 guesses in the worst case, let alone any form of proof. Inaddition, Alex proved that among trees with 7 guesses in the worst case,the best possible average number of guesses is 4.52629 (only leavingopen the possibility of improving the average by sacrificing the worstcase).
Fixed guesses
Added 2022-03-02. Instead of using a decision tree,one could consider the following problem. Let us assume that we willplay, at first, a fixed set of guesses, blindly, without observing thegame’s answers. Could we find such a set of guesses such that,afterwards, the answers immediately let us infer the secret word? Thiscan be seen as an “offline” or “blindfold” variant of the solutionapproach.
Exploiting the 2309-words solution list, Alexandre Salle showed that it can be donewith 8 fixed guesses plus the winning guess, so 9 guesses in total.It is unknown whether this is optimal. In particular, it is an openquestion whether a winning purely-offline strategy can exist within 6guesses.
Update 2022-04-08: Virgile Andreani found a set of6fixed guesses that lets you win with the seventh, thus very close tosystematically winning Wordle in 6 turns with fixed guesses!
Update 2022-05-12: David Rusin consideredthe problem of picking fixed guesses exclusively from the 2309-wordsolution list. Remarkably, despite the much more constrained setting, he also found a setof 6 fixed guesses.
Update 2022-05-18: Thanks to David’s work, we nowknow that the above results with 6 fixedguesses are optimal. It is thus impossible to solve Wordle within 6guesses with the fixed-guesses approach (5 fixed guesses + 1 winningguess).
Update 2022-08-13: It turns out that David’s set of6 words is the uniquesolution to the problem of solving Wordle after 6 fixed guesses from the2309-word solution list. Using a MIP formulation, he showed that it isimpossible to find such a set if any single one of those 6 words isdisallowed as a guess.
Update 2022-08-20: If we do not exploit the2309-words solution list, we need 10 fixedguesses plus the winning one, so 11 guesses in total. This isoptimal.
Hybrid approaches
Added 2022-11-17. We know that it is not possible tosingle out the secret word after 5 fixed guesses. However, one mayattempt to play fewer than 5 fixed guesses, then allow small decisiontrees afterwards to try and win Wordle within 6 guesses. That is exactlywhat IouriKhramtsov proposes, with the four fixed guessesslant, price, dough, balmy, which allows us to always winWordle by subsequently following small depth-2 decision trees. Anothersuch option is bawdy, flung, porch, smite.
David Rusin subsequently improved on those fixed guesses in twodistinct ways. First, he found that in this context, 3 fixed guesses areenough! Specifically, it is possible to start with 3 fixed guesses, thenfollow depth-2 decision trees, to always win Wordle within 5 totalguesses. Through exhaustive search, he even determined that exactly261 such sets of 3 fixed guesses exist. It is remarkable that 5total guesses is achievable in such a restricted context, given thateven using full decision trees, 5 guesses is optimalfor Wordle in terms of tree depth.
The second improvement is more subtle. The depth-2 decision treesabove can have an arbitrary number of nodes and can involve arbitraryguesses. In particular, such tree may even require playing guess wordsthat are incompatible with the previous answers. Things would be easierfor a human player if they could greedily play any of the remainingpossible solutions (i.e., any word compatible with the previousanswers), and be guaranteed to find the secret word within 6 guesses.David found that if we start with the4 fixed guesses carve, downy, plumb, sight, it isindeed possible to win Wordle in all cases within 6 guesses bysubsequently playing any of the remaining possible secret words. He alsoproved that this isunachievable with 3 fixed guesses.
Note that both improvements take place in a restricted context inwhich only potential secret words are allowed as guesses (there are only2309 such words, as opposed to the full 12972-word dictionary of5-letter combinations normally allowed as guesses).
Computational complexity
Added 2022-04-08 At FUN 2022, Daniel Lokshtanov and Bernardo Subercaseaux willpresent their paper onthe computational complexity of Wordle.
In order to study the complexity of Wordle, we need to formalize theproblem. In particular, we need to specify its input. Indeed, asenvisioned by its creator, all the parameters of the game are fixed: Thealphabet Σ contains 26 letters, the number of lettersk in a word is 5, and the dictionary D contains 12972words. We need to consider some or all of those as our input. Otherwise,from a complexity perspective, all the methods deployed above to findoptimal decision trees are constant-time, O(1) algorithms. Inparticular |Σ| and k should not both be constant since|D| is upper-bounded by |Σ| to the powerk.
Daniel and Bernardo show that even consideringjust Σ and D as our input (leaving k fixed to5), as well as an integer ℓ, it is NP-hard to decide whether adecision tree with ℓ worst-case guesses exists. In thatcontext, in particular, finding an optimal decision tree (onecorresponding to the smallest value of ℓ for which the answeris yes) is NP-hard.
On the other hand, they also show that if |Σ| is constant,one can solve the above decision problem in polynomial time. They firstconstruct a strategy that can always solve the game in |Σ|guesses. This handles all the cases in which ℓ ≥ |Σ|: theanswer is always yes. Then, if ℓ < |Σ|, we have thatℓ is upper-bounded by a constant, essentially removing theexponential character of decision tree enumeration.
