# Wordle-solving state of the art: all optimality results so far

Almost all mathematical questions one could have about Wordle are
**settled** by now. I summarize here what is known so
far.

## tl;dr

- If we exploit the 2309-words solution list:
- Wordle can be 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 of average, and in the worst case: It was proven 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, even independently. - In hard mode, Wordle can
be solved in 3.5076 guesses on average (with 6 guesses at worst,
i.e. 100% of the time). Or, with a
*different*decision tree, it can be solved with a slightly worse average, but always within 5 guesses. Again, both trees are*optimal*for their respective objective functions. - Instead of using a decision tree, we can also consider the problem
of solving the game starting with a
*fixed*set of guesses independent of the game’s answers. This can be done with 7 total guesses (6 fixed guesses plus the winning guess), even if we only allow guess words from the 2309-words solution list. This result is optimal: it is impossible to play 5 fixed guesses, 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), with 4.07771 guesses on average.
- In terms of the worst case, the above result is
*optimal*: It was proven that it is not possible to find a decision tree whose worst case is 5 guesses or less. - In terms of the average, 4.07771 is not proven optimal, but there is strong evidence suggesting that it probably is.
- In hard mode, Wordle can be solved
in 7 guesses worst, 4.52629 guesses on average. The worst case is
*optimal*: Hard mode Wordle cannot be solved 100% of the time within 6 guesses. Moreover, the 4.52629 average cannot be improved while maintaining the 7-guesses worst case. - Alternatively, we can play 10 fixed guesses, then always win with the 11th. This is optimal.

- In terms of computational complexity:
- If we abstract away the dictionary and the alphabet (our input), finding an optimal strategy is NP-hard.
- However, if we fix the alphabet size, it can be done in polynomial time.

Note that the New York Times bought Wordle and tweaked the word lists on two occasions. Ultimately (since 2022-03-16), their changes amount to removing 6 words from the original solution list (now 2309 words), while retaining them as allowed guess words. The results above were updated for the latest word lists.

**Update 2022-08-20**: The NYT has added two words to
the list of allowed words. While this should have limited impact on the
results 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 is allowed to use as guesses. They are essentially all 5-letter combinations one could reasonably argue are English words. The “secret” word that the player has to discover is also always in that dictionary.

It is so trivially easy to cheat at Wordle that there is no point to it: The list of secret words is right there in the code of the game. The daily secret words are picked sequentially from that list, so they are all known since 2021-06-19 (“cigar”) and until

~~2027-10-20~~2027-10-14, for a total of~~2315~~2309 scheduled secret words.One could always look up that list for the current date and solve the game immediately at the first guess. However, this is not much fun (mathematically), so we need to define the game somehow. There are two obvious options:

**“Full dictionary”**: we consider that the secret word could be any word from the full 12972-word list.**“Solution list”**: we know that not every word can be a secret word, and take advantage of the knowledge of the list of 2309 scheduled secret word (but we ignore its order, which would trivially allow us to win every game in one guess).

While many focused on finding the best “first word” to play as a guess, the first guess is just a tiny part of what we really want: A

**decision tree**. A decision tree not only tells you which guess to play first, but accompanies you as you play, telling you which guesses to play subsequently*in function of*the information given you by the game as you play (i.e. all the letter colors 🟩🟨⬜ so far). I only cover here fixed/deterministic decision trees, which will always reach a given secret word in the same way, because it is straightforward to give formal evaluations of how good they are. I will also briefly touch on approaches to solve the game without decision trees, with a fixed set of guesses.The word

**optimal**has taken quite a mauling lately in Wordle-related writings. Just to be to be absolutely clear, a solution is optimal only if no better solution can possibly exist. In particular, there is no such thing as a “more optimal” solution.Now, regarding what we optimize, there are two natural choices:

The

**worst-case**number of guesses. That is, given a decision tree, what is the maximum number of guesses necessary to correctly guess any secret word? In other words, after how many guesses does the decision tree guarantee that we win the game?The

**average**number of guesses. What is the average, over all possible secret words, of the number of guesses a decision tree will take to get a win?

As we will see, those are competing objectives, sometimes irreconcilably, sometimes not so.

Buried in the options, Wordle features a

**hard mode**. The game is different in hard mode, in that only words that satisfy the hints given earlier are allowed as player guesses. (For example, if a letter is colored green 🟩 after one guess, that letter must be present in the same position in all subsequent guesses.)There are subtleties about the rules regarding words with repeated letters, and this particularly affects hard mode. However, it seems that by now everyone agrees what the rules are.

## Solution list: 2309 possible secret words

In this section, we assume that we know the list of 2309 scheduled secret words, but we ignore the list’s order (it would be trivially easy otherwise).

For the original word list, Cyrus Freshman set up a nice automated leader board with a standardized input format. There, we can directly find that fourteen distinct people have found decision trees that solve Wordle in 3.4212 average guesses and (simultaneously) 5 worst-case guesses (i.e., 100% of the time, never even using the 6th guess), including Jonathan Olson, Peter Tseng and Alex Selby. With the updated word list, we get an average of 3.4201 guesses, still with 5 guesses in the worst case.

While I suspect all employed similar general approaches (recursive
enumeration / backtracking with tree pruning and some form of caching),
I will now mainly defer to Alex
Selby’s nice
writeup, because it is the most thorough and because the
corresponding code can answer more of our questions. Alex and Peter both
implemented their algorithms in such a way that not only they get good
decision trees, but they can also subsequently perform an accelerated
*complete* enumeration and prove optimality (no tree has an
average of less than 3.4212, and no tree wins all games in 4 guesses at
most). Alex indicates that the latter is by far the most difficult part
computationally: finding good trees (that happen to be optimal) is
quick, proving that they are indeed optimal is much more expensive.

For hard mode, both Alex and Peter found a decision tree with in 3.5085 guesses on average and 6 guesses at worst (i.e., 100% wins in 6 guesses), 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 the worst case: Alex found a different decision tree with 3.5448 guesses on average, but a worst case of 5 guesses! Again, Alex reports optimality on both fronts. With the updated word list, the average becomes 3.5076 with a worst case of 6, while again a worst case of 5 is possible.

## Full dictionary: 12972 possible secret words

In this section, we assume that the game can pick secret words from its whole 12972-word dictionary. The number of potential secret words is now about 5.6x as large as in the previous case, dramatically increasing the size of an already large enumeration space.

Still, the same type of emumeration / backtracking tricks work even in 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 thus still possible to win every Wordle game within the 6 allowed guesses! I did not try to optimize for the average number of guesses, but it can still be measured: 4.2308 guesses on average over the 12972 words. I was not able to perform complete enumeration for 5 guesses, so there was no optimality guarantee. However, complete enumeration did rule out the existence of trees with 4 guesses in the worst case, leaving a frustrating gap between 4 and 6.

The frustration was short-lived, fortunately, as Alex Peattie proved that it is impossible to build a decision tree with 5 guesses in the worst case, making the result sharp. The proof is much more interesting than complete enumeration: it relies on cleverly finding provably-difficult-to-disambiguate word subsets and it can 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 terms
of the worst case at 6 guesses. It is still an open question whether we
can find a decision tree that is optimal in terms of its
*average* number of guesses.

**Update 2022-02-06** Mark
Fisher found a different decision tree with 6 guesses in the worst
case. His approach is much less brute-force than mine and as a result he
has nice
insights about which words are difficult to disambiguate, and how to
tackle such word groups.

**Update 2022-04-08** Alex Selby improved his code (by
two orders of magnitude!) and applied it to the full dictionary as well.
This let him find a
tree that solves wordle in 4.07771 average guesses (6 in the worst
case). While there is no proof that 4.07771 is optimal, there is a good
argument to be made that it probably is: Alex managed to show that if we
fix the first guess word, this tree is the best one in terms of average
number of guesses. Furthermore, this first guess word was deemed the
most 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 a tree that solves wordle in 7 guesses in the worst case and proved by complete enumeration that 6 worst-case guesses is impossible! To give you an idea of the achievement here, my own code could only find a tree with 14 guesses in the worst case, let alone any form of proof. In addition, Alex proved that among trees with 7 guesses in the worst case, the best possible average number of guesses is 4.52629 (only leaving open the possibility of improving the average by sacrificing the worst case).

## Fixed guesses

**Added 2022-03-02**. Instead of using a decision tree,
one could consider the following problem. Let us assume that we will
play, at first, a fixed set of guesses, blindly, without observing the
game’s answers. Could we find such a set of guesses such that,
afterwards, the answers immediately let us infer the secret word? This
can be seen as an “offline” or “blindfold” variant of the solution
approach.

Exploiting the 2309-words solution list, Alexandre Salle showed that it can be done with 8 fixed guesses plus the winning guess, so 9 guesses in total. It is unknown whether this is optimal. In particular, it is an open question whether a winning purely-offline strategy can exist within 6 guesses.

**Update 2022-04-08**: Virgile Andreani found a set of
6
fixed guesses that lets you win with the seventh, thus very close to
systematically winning Wordle in 6 turns with fixed guesses!

**Update 2022-05-12**: David Rusin considered
the problem of picking fixed guesses exclusively from the 2309-word
solution list. Remarkably, despite the much more constrained setting, he also found a set
of 6 fixed guesses.

**Update 2022-05-18**: Thanks to David’s work, we now
know that the above results with 6 fixed
guesses are optimal. It is thus impossible to solve Wordle within 6
guesses with the fixed-guesses approach (5 fixed guesses + 1 winning
guess).

**Update 2022-08-13**: It turns out that David’s set of
6 words is the unique
solution to the problem of solving Wordle after 6 fixed guesses from the
2309-word solution list. Using a MIP formulation, he showed that it is
impossible to find such a set if any single one of those 6 words is
disallowed as a guess.

**Update 2022-08-20**: If we do *not* exploit the
2309-words solution list, we need 10 fixed
guesses plus the winning one, so 11 guesses in total. This is
optimal.

### Hybrid approaches

**Added 2022-11-17**. We know that it is not possible to
single out the secret word after 5 fixed guesses. However, one may
attempt to play fewer than 5 fixed guesses, then allow small decision
trees afterwards to try and win Wordle within 6 guesses. That is exactly
what Iouri
Khramtsov proposes, with the four fixed guesses
`slant, price, dough, balmy`

, which allows us to always win
Wordle by subsequently following small depth-2 decision trees. Another
such option is `bawdy, flung, porch, smite`

.

David Rusin subsequently improved on those fixed guesses in two distinct ways. First, he found that in this context, 3 fixed guesses are enough! Specifically, it is possible to start with 3 fixed guesses, then follow depth-2 decision trees, to always win Wordle within 5 total guesses. Through exhaustive search, he even determined that exactly 261 such sets of 3 fixed guesses exist. It is remarkable that 5 total guesses is achievable in such a restricted context, given that even using full decision trees, 5 guesses is optimal for Wordle in terms of tree depth.

The second improvement is more subtle. The depth-2 decision trees
above can have an arbitrary number of nodes and can involve arbitrary
guesses. In particular, such tree may even require playing guess words
that are incompatible with the previous answers. Things would be easier
for a human player if they could greedily play any of the remaining
possible solutions (i.e., any word compatible with the previous
answers), and be guaranteed to find the secret word within 6 guesses.
David found that if we start with the
4 fixed guesses `carve, downy, plumb, sight`

, it is
indeed possible to win Wordle in all cases within 6 guesses by
subsequently playing any of the remaining possible secret words. He also
proved that this is
unachievable with 3 fixed guesses.

Note that both improvements take place in a restricted context in which only potential secret words are allowed as guesses (there are only 2309 such words, as opposed to the full 12972-word dictionary of 5-letter combinations normally allowed as guesses).

## Computational complexity

**Added 2022-04-08** At FUN 2022, Daniel Lokshtanov and Bernardo Subercaseaux will
present their paper on
the computational complexity of Wordle.

In order to study the complexity of Wordle, we need to formalize the
problem. In particular, we need to specify its input. Indeed, as
envisioned by its creator, all the parameters of the game are fixed: The
alphabet *Σ* contains 26 letters, the number of letters
*k* in a word is 5, and the dictionary *D* contains 12972
words. We need to consider some or all of those as our input. Otherwise,
from a complexity perspective, all the methods deployed above to find
optimal decision trees are constant-time, *O(1)* algorithms. In
particular *|Σ|* and *k* should not both be constant since
*|D|* is upper-bounded by *|Σ|* to the power
*k*.

Daniel and Bernardo show that even considering
just *Σ* and *D* as our input (leaving *k* fixed to
5), as well as an integer *ℓ*, it is NP-hard to decide whether a
decision tree with *ℓ* worst-case guesses exists. In that
context, in particular, finding an optimal decision tree (one
corresponding to the smallest value of *ℓ* for which the answer
is 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 first
construct a strategy that can always solve the game in *|Σ|*
guesses. This handles all the cases in which *ℓ ≥ |Σ|*: the
answer is always yes. Then, if *ℓ < |Σ|*, we have that
*ℓ* is upper-bounded by a constant, essentially removing the
exponential character of decision tree enumeration.