Beating Wordle: Constraint Programming | by Asim | Feb, 2022

To beat wordle, we must find a list of English words, luckily after searching GitHub I landed on this beauty.

As recommended by the repo I choose the words_alpha.txt, feel free to choose your own. Now we have a list of English words we can move on to the next step.

So now we have some words, let’s import them into Python and have a look at them. For this, we can use Pandas to read the data.

That is very cool we can see we have 370,103 words. Now let’s just get the 5 letter words.

Yay! We now have 15,918 words to play with, some of these words I have never heard of like aalii which means “a bushy sapindaceous shrub”.

Now we have got lots of words we need a way for the solver to understand. A CSP solver can understand a few data types like Integras and Booleans. But the solver I will be using does not understand characters so we need to convert the characters into something they can understand.

We could use one-hot encoding. Or we could keep it simple and assign each letter a number (eg the letter a → 0, b → 1 … z → 25), which is a lot simpler. So let’s do that.

When we run this code we get a variable called words which is a list of words represented by integers. For example, [0,0,7,4,3] represents “aahed”.

Now we need to get into the weeds a bit. We want to define some variables for our constraint solver to understand. The constraint solver we are going to use is called Cadical — it is one of the state-of-the-art solvers.

To write for Cadical actually takes a long time so instead, we are going to use an abstraction called SavileRow which runs on the Essence Prime language and then can translate our code to Cadical which it can then solve.

First, we need to tell SavileRow what our parameters are. To make this efficient we can write a Python function that will take the words variable and spit out a .param the file that SavileRow can understand.

In this function, we pass to SavileRow the number of words, number of letters of words, and the number of words we want the solver to pick for us.

As we promised at the top of this article we are going to be comparing 2000 words. So let’s randomize the words so when we pass it to the function it has a mixture of words starting with different characters.

random.shuffle(words)

We can now pass words into the function. And we get this as our param file:

For the solver to pick the best words we need to tell the solver what to find. We can tell the solver what to find by the find command. In this case, we want to find the indexes of the best words which have the best characteristics for finding a wordle word. We can call this array best_words

The heuristic is the most important of constraint programming this is what we are trying to optimize. Here we are trying to optimize the likelihood that two of the words cover the target word. In effect, we want to count how many times both of these words letters are in every other letter. We can call this a variable cost we can tell the solver to maximise this.

As for the constraints we want to make sure all the words chosen by the solver are different we can use the AllDiff constraint for that. We also want to make sure that the solver does not come up with the same solution twice, eg if indexes chosen are:[1,3] then [3,1] is the same solution just in a different order. We can force order by constraining that the bigger index always comes first.

With all of that, we can create a SalvileRow model:

After running the solver using the command:

savilerow words.eprime words.param -run-solver -sat

We get an output of [414, 129] , these are indexes of the words which have the highest score on the heuristic. If we then look up these words we get [11, 0, 20, 13, 3] and [14, 18, 8, 4, 17] when translated back into characters we get ‘laund’ and ‘osier’

̶S̶o̶m̶e̶ ̶o̶f̶ ̶t̶h̶e̶ ̶w̶o̶r̶d̶s̶ ̶i̶n̶ ̶t̶h̶e̶ ̶w̶o̶r̶d̶s̶_̶a̶l̶p̶h̶a̶.̶t̶x̶t̶ ̶d̶o̶ ̶n̶o̶t̶ ̶a̶p̶p̶e̶a̶r̶ ̶t̶o̶ ̶b̶e̶ ̶c̶o̶m̶p̶a̶t̶i̶b̶l̶e̶ ̶w̶i̶t̶h̶ ̶W̶o̶r̶d̶l̶e̶, ̶ ̶s̶o̶ ̶i̶t̶ ̶m̶a̶y̶ ̶n̶o̶t̶ ̶b̶e̶ ̶a̶c̶c̶u̶r̶a̶t̶e̶ ̶f̶o̶r̶ ̶w̶o̶r̶d̶l̶e̶.̶ ̶I̶f̶ ̶a̶ ̶d̶a̶t̶a̶s̶e̶t̶ ̶o̶f̶ ̶w̶o̶r̶d̶l̶e̶ ̶w̶o̶r̶d̶s̶ ̶t̶h̶a̶t̶ ̶a̶r̶e̶ ̶u̶s̶e̶d̶ ̶i̶s̶ ̶e̶v̶e̶r̶ ̶r̶e̶l̶e̶a̶s̶e̶d̶ ̶t̶h̶e̶n̶ ̶a̶n̶ ̶a̶c̶c̶u̶r̶a̶t̶e̶ ̶a̶n̶s̶w̶e̶r̶ ̶c̶a̶n̶ ̶b̶e̶ ̶r̶e̶a̶c̶h̶e̶d̶ ̶o̶n̶ ̶w̶h̶i̶c̶h̶ pie-o-r-d-s- pie-r-e- _b-e-s-t- _f-o-r- pie-c

Leave a Comment