25 Unique Letters

Recently, Matt Parker made a YouTube video about finding 5 English words,1 each 5 letters, with 25 unique letters. He wrote a Python script which took about a month to run. He didn’t optimize further because he had better things to do with his time. Benjamin Paassen outdid him, taking only 22 minutes. Their approach was to construct a graph where each node represented a word and words with distinct letters are connected by an edge. Then, the problem reduces to finding a 5-clique, which can be solved with 5 nested for loops.

I realized that the problem also reduces to exact cover, and I had an exact cover solver lying around from polycube. I took about an hour to code this. Here’s a demo:

$ time parker | head
831 solutions.

real    0m34.289s
user    0m34.288s
sys     0m0.001s

I could optimize it further, or even use a better exact cover solver from the internet, but I have better things to do with my time.

The connection to Wordle is interesting. Using fjord, gucks, nymph, vibex, and waltz as your opening guesses is not a good idea since you’ll only have one guess left, and that set of guesses can’t distinguish three from ether, for example.2 This raises the question: Is it possible to win Wordle every time with a strategy that keeps the first 5 guesses constant?

  1. An “English word” is one found in the infamous words_alpha.txt

  2. Yes, you’ll also need at least 6 guesses most of the time, but considering that shortcoming has already been done. 

04 August 2022