Can we always solve Wordle “offline” with fixed guesses?

2022-05-18 (last updated 2022-11-17)

tl;dr

No, but almost.

Alexandre Salle, Virgile Andreani and David Rusin found multiple strategies that solve all Wordle puzzles “offline” in as low as 7 guesses (6 fixed guesses + 1 winning guess).

With a set-cover formulation and a MIP solver, it can be shown that it is impossible to do the same within 6 guesses. In that sense, the above strategies are thus optimal for offline Wordle.

If we do not exploit the 2309-word solution list, we need 11 guesses (10 fixed guesses + 1 winning guess).

Using fixed guesses: offline Wordle / blindfold Wordle

Back in February, Alexandre Salle proposed an interesting Wordle-solving challenge: Can we solve every Wordle puzzle with a fixed set of initial guesses? Specifically, the challenge is as follows. Find $f$ words such that:

• We always play those same $f$ words as our initial guesses, without looking at the game’s answer.
• Then, after the $f$th guess, we observe the game’s answers and infer the secret word.
• At the $(f + 1)$th guess, we always correctly find the secret word.

Alexandre refers to this as solving Wordle offline, as opposed to using a decision tree. Indeed, a decision tree can tailor each guess online knowing the game’s answer to previous guesses, to improve our chances of winning quickly. An “offline” approach is much more constrained. The term blindfold Wordle, to describe the same problem, is due to Alex Selby.

The question here is: What is the value of $f^*$, the smallest $f$ such that an offline strategy exists? In particular, can we find a strategy with $f \leq 5$ fixed guesses? Together with the final (non-fixed, winning) guess, this would mean winning 100% of the 2309 Wordle puzzles within the 6 allowed guesses. Note that at first, we will exploit the fact that, among the 12974 allowed guess words, only 2309 are possible secret words.

Upper bounds on $f^*$

In his February post, Alexandre found a first strategy with $f=8$ fixed guesses. In March, Virgile Andreani found a set of 7, then $f=6$ fixed guesses that lets you win with the seventh, thus tantalizingly close to our objective of always winning Wordle in 6 turns with fixed guesses! In May, David Rusin found another 6-fixed-guesses strategy, but one which satisfies an additional constraint: David’s guess words are picked exclusively from the 2309-word solution list (the solution lists only features fairly common words, whereas the validity of some of 12974 dictionary words may be debatable). The fact that $f=6$ is possible in such a restricted setting gives hope for an $f=5$ strategy, but none had been found.

Lower bounds on $f^*$

When Alexandre told me about solving Wordle offline, I briefly considered formulating it as a satisfiability (SAT) or mixed-integer programming (MIP) problem. Unfortunately, any formulation I came up with had either too many variables, or too many constraints to even fit in memory – let alone be solved.

But then recently David Rusin kindly explained to me his approach. In the process of finding his set of 6 fixed guesses, he meticulously determined a list of 916 pairs of words that are somehow very similar in terms of Wordle’s answers, hence difficult to disambiguate with Wordle guesses (he calls them toughpairs). This opens up a new possibility.

Indeed, the problem of determining the Wordle secret word with $f$ fixed guesses can be stated as follows. We are guaranteed to discover the secret word if and only if, for every possible pair of possible secret words, one of our $f$ guesses gets a distinct game answer for the two words in the pair. In other words, for every pair of words, we must disambiguate between them with at least one of our guesses.

This is a very straightforward set-cover problem; it would make a great first exercise in an introductory optimization class. We have 12974 binary variables, one for each possible word. We decide that each will take a value 1 if we use the corresponding word as a guess, 0 otherwise. We will minimize $f$, whose value is the sum of our variables. Then, we have one constraint for every possible pair of secret words, stating that among all the guesses that disambiguate between those two secret words (i.e. the variables that cover this pair), at least one must be taken.

In mathematical terms, our model takes the following form. Let $W := \{ 1, \ldots, 12974 \}$ be the index set of all words, and let $P := \left\{ 1, \ldots, \frac{2309 (2309 - 1)}{2} \right\}$ be the index set of all the possible pairs of secret words. We construct a constant matrix $A \in \{ 0, 1 \}^{|P| \times |W|}$ that satisfies $$A_{ij} = \left\{ \begin{array}{ll} 1 & \text{ if the guess word } j \in W \text{ would yield} \\ & \text{ a distinct answer for the two} \\ & \text{ hidden words in the pair } i \in P, \\ & \\ 0 & \text{ otherwise.} \end{array} \right.$$ The model is then the usual set-cover formulation $$\begin{array}{rrrcll} f^* = \min & \displaystyle \sum_{j \in W} & x_j & & \\ \text{s.t.} & \displaystyle \sum_{j \in W} & A_{ij} x_j & \geq & 1, & \forall i \in P \\ & & x_j & \in & \{ 0, 1 \}, & \forall j \in W \end{array}$$ or, more concisely, $$\begin{array}{rrcl} f^* = \min & 1^T x & & \\ \text{s.t.} & A x & \geq & 1 \\ & x & \in & \{ 0, 1 \}^{|W|}. \end{array}$$

Unfortunately, our MIP model has $|P| = \frac{2309 (2309 - 1)}{2} = 2,664,586$ constraints, one for each pair of words. The performance of MIP solvers these days is fantastic, but two million constraints is still rather large for a MIP formulation.

However, we can construct a relaxation of this problem, by considering only $|P'| = 916$ constraints, where $P'$ is the set of David’s carefully curated “toughpairs”. Using just those 916 pairs (instead of 2,664,586) as our set-cover constraints, we obtain a relaxed model that is much more amenable to tackling with a MIP solver. David kindly provided me with the matrix $A' \in \{ 0, 1 \}^{|P'| \times |W|}$. You can download the resulting LP file here. All I did is feed it to Coin-OR’s open-source MIP solver Cbc, and it returned an optimal solution of value $f^*=6$ after 83 seconds. In other words, with $f<6$ guesses, it would be impossible to disambiguate between David’s 916 pairs of secret words, let alone solve Wordle entirely.

Update 2022-08-13: Using this MIP approach, David Rusin also showed that, in the context of picking the guesses exclusively from the 2309-word solution list, his solution is actually unique. He proceeded by solving 6 MIPs, in each one removing one of his 6 words from the allowed guesses. In each case, it became impossible to identify the secret word within 6 fixed guesses.

Targeting the full 12974-word dictionary

Added 2022-08-20. In an email conversation spurred by Mark Fisher’s interest in $k$-Wordle Alex Selby pointed out a link between $k$-Wordle and offline/blindfold Wordle. In $k$-Wordle, one finds $k$ secret words simultaneously with a single set of guesses. After each guess, the game provides $k$ answers, one corresponding to each secret word. Many such games can be found on the web, for example dordle for $k=2$, or sedecordle for $k=16$.

Alex’s link is that $f^* + k$ is an upper bound on the number of guesses necessary to solve $k$-Wordle. Indeed one can play the fixed set of $f^*$ guesses as if playing offline Wordle. Then, the information gathered should be sufficient to solve all $k$ puzzles in one guess each.

Mark is interested in bounds for $k$-Wordle targeting the full 12974-word dictionary (i.e., not exploiting the 2309-word solution list), so I tried to apply the same MIP approach to this case. Unfortunately, I did not have David Rusin’s “toughpairs” for the whole dictionary, so I adopted the following approach:

1. Start with a candidate set of offline guesses (initially, David’s 6 guesses).
2. Determine all the sets of secret words $S_1, S_2, \ldots \subseteq W$ that are not disambiguated by those offline guesses. If we play those guesses, the game’s answers will be identical for any secret word $s \in S_1$. Same for any $s \in S_2$, and so on.
3. For every $u$ such that $|S_u| \geq 2$, add $\{ (s, t) \; : \; s, t \in S_u, \, s < t \}$ to our list of toughpairs.
4. Build a set-cover formulation with one constraint per toughpair.
5. Feed the formulation to a MIP solver, get a new candidate set of offline guesses, go back to 1.

After 8 iterations of this process, I obtained 4936 pairs, but unfortunately the MIP solves were exceeding an hour, while only adding a few dozen pairs to the formulation each time. However, a clear pattern was emerging. Most pairs were composed either (a) of words that differed only in one letter position, or (b) of words that were permutations of each other’s letters. We need to strike a balance here. Adding all such pairs yields a gigantic MIP formulation (a 2.2 GB lp file!) that cannot be solved. Adding too few would not sufficiently accelerate the above iterating process. After some attempts, I settled on all 2721 pairs of words that differed in at most two positions and were composed of the same letters. Adding them to the list of pairs already found, I obtained a set-cover formulation with 12974 variables and 6890 constraints. It was solved in a few hours, giving the 10 fixed guesses:

defer myrrh going ajwan beaux klett punny spods villi zocco

This solution is not necessarily the only one with 10 fixed guesses, but the MIP solver did prove optimality (i.e., 9 is impossible). Counting the final correct guess, we thus need 11 guesses to solve offline Wordle if we don’t exploit the 2309-word solution list. Coming back to $k$-Wordle, Alex’s strategy now provides an upper bound of $10 + k$ guesses.

Conclusion

The strategies found by Virgile Andreani (combo, fatty, grrrl, spuds, venge, whilk), and David Rusin (catty, frond, rumba, spill, verge, whack), which solve Wordle offline within 7 guesses, are optimal. It is impossible to solve Wordle offline within 6 guesses.

The next best thing, however, is still possible: One can solve all the Wordle puzzles with a hybrid approach starting with 3 initial fixed guesses, then following multiple tiny 2-deep decision trees.

And if you prefer full-on decision tree approaches, see my Wordle-solving state of the art survey.