Introduction

This week the Riddler takes on Wordle. Many of your social media feeds have likely been bombarded by images like this, showing the meandering path from first guess to solution, and you may have even played the game yourself.

• Wordle 208 4/6
• ⬜🟨🟨⬜⬜
• 🟨🟨⬜⬜⬜
• 🟩🟩🟨⬜⬜
• 🟩🟩🟩🟩🟩

I've enjoyed playing Wordle over the last few weeks too. My strategy is loosely guided by what I learned when the Riddler tackled Lingo - a similar word guessing game, but so far I've left the dictionary and code off to the side. It was only a matter of time before Riddler Nation asked what an optimal strategy might look like. As a result, this week, we're given the following task.

Your goal is to devise a strategy to maximize your probability of winning Wordle in at most three guesses. In particular, please describe:

1. your strategy
2. the first word you would guess
3. your probability of winning in three or fewer guesses

To help us with this week's puzzle, we're allowed to use Wordle's lists of valid guesses (12,972 words) and daily solutions (2,315 words). Note, the guess list includes all words from the solutions list.

Setup

Before diving into the code and the solution, let's outline the concepts we need to solve this problem. The first key concept is something I'll call a partition.

A partition is the set of words that are still candidates to solve the puzzle, given the clues we have from our previous guesses. When we start the game, before making any guesses, all 2,315 words belong to a single partition, because any one of them could be the solution. When we guess new words, we shrink the partition as we learn new clues about the secret word. Hopefully, by the end, we'll have a partition with a single word, which is the secret word.

We can start asking interesting questions about partitions, like "what word will split this partition into the most sub-partitions?" With a bit of code, we can identify all the partitions that a given guess will create. For example, suppose our first guess is the word PARSE. Let's consider a few possible scenarios.

1. None of the letters are a match (as in BUILT).
   • We know the secret word belongs to a partition of 270 words.
   • The best next guess is the word CLINT, which subdivides the 270 words into 82 new partitions.
   • Our average win rate simplifies to 82/270, or ≈30%.
   • If the secret word were BUILT, we would have narrowed it down to {BUILT, GUILT, QUILT}, and we would guess randomly.
2. There is a P in the secret word, but it's not the first letter, and no other letters match (as in TOPIC).
   • We know the secret word belongs to a partition of 25 words.
   • The best next guess is the word DIMLY, which subdivides the 25 words into 21 new partitions.
   • Our average win rate simplifies to 21/25, or 84%.
   • If the secret word were TOPIC, we would have narrowed it down to {INPUT, OPTIC, TOPIC, UNZIP}, and we would guess randomly. (One of the unlucky cases in this set.)
3. The letters A, R, and E are correct and in the right position, and no other letters match (as in BARGE).
   • We know the secret word belongs to a partition of 4 words.
   • There are many equally good next guesses, but the first in alphabetical order is ALECK, which gives us enough information to create four partitions with a single word in each, guaranteeing a solve in three guesses.
   • Our average win rate will be 100%!

Now that we understand partitions, let's review how we can use them to devise a strategy.

Strategy

Let's assume we're about to make our third guess. We will have a partition of words with size $N$. If we're lucky enough to have a partition with a single word, we will win the game. However, if we have a partition of size $N > 1$, then we have to guess randomly, and we will win with probability $1 / N$. In any case, there is virtually no strategic decision when it comes to the third guess; we just pick a random word from the partition. Therefore, our goal should be to identify second guesses that maximize the number of partitions for our third guess, because it means each partition will be small and will give us the best chance to win.

Consequently, we want to pick first guesses that make our second guesses more effective. Roughly speaking, we want to search all possible first guesses, knowing how we'll handle second and third guesses based on the results. This is much easier said than done!

While I was able to get an answer that seems promising, I have a feeling there are a few small optimizations I may have missed, faster code I could have written, and larger groups of words I could have searched. But, caveats aside, let's proceed to the solution itself.

Solution

Rather than follow a true dynamic programming approach, which would have taken too long to calculate, I used a few heuristics. First, I calculated the number of partitions each word would produce if it were guessed first. For example, PARSE creates 146 partitions. That's good, but the best I found was the word TRACE, which splits the solutions into 150 partitions, two better than the next best words, CRATE, and SALET. I wasn't able to prove exhaustively that these words are the optimal starting words, but they seemed like a great place to start.

Next, assuming that I chose TRACE as my first word, I went through each of the 150 partitions and chose the second word that splits each one into the most sub-partitions. Finally, I calculated the win probability based on the partition size for each of my third guesses.

This strategy produces a win rate of $\frac{1327}{2315}$, or roughly 57.3%.

At various points in my code I trimmed the list of words to search, hoping to produce results in a reasonable amount of time. However, I believe these shortcuts likely led to suboptimal performance. A true solution would consider the full set of valid guess words at each stage, and would result in a truly optimal strategy.

Given a bit more time and some more careful code, I think there is more performance to eek out of my algorithm. In any case, I enjoyed the challenge this weekend, and look forward to spare moments in the future when I can revisit this puzzle and improve my result.

Fun Facts

Here are some of the best and worst words, based on the number of partitions they create as a first guess.

Word	Partitions
TRACE	150
CRATE	148
SALET	148
SLATE	147
REAST	147
PARSE	146
...	...
OZEKI	44
WAQFS 1	42
SQUIZ	39

Full Code

Fortunately I was able to reuse much of the code I wrote to solve Riddler Lingo a year ago. But a single weekend wasn't quite enough to write the polished code I would have preferred. Instead, I have a lot of scratch work that I'll try to clean up when I have a moment and add it here.

Footnotes

1. Yep, this is actually a valid Wordle guess. ↩