Words With Friends Solver

posted in Python at 04 September 2017

For my A-level Computing project, I worked on a rudimentary Words With Friends solver. When emailed a screenshot from a particular size of phone (and given the letters to make a word from), it not only gives the best move (and may do so from a dictionary of commonly used words or a full dictionary), but also gives hints. Here's an example of the output it gives:

Hint #1: The best move is located in the top-left quadrant, attached to (or creating the word GI). If you're only looking at commonly used words, the best move is in the bottom-left quadrant, attached to (or creating) the word DO...

How does this work? It is split into three parts: image processing, email processing and the actual solver.

Processing an Image

The first thing the program does when receiving an email is take the screenshot and convert the grid shown in the screenshot to a Python array. This is the most rudimentary bit - in the program we have black and white images for every letter, so we simply compare predefined sections of the image to those and look for the closest fit. These predefined sections have been found by hand - as the aim was for this to only work with one screen size, everything will always be in the same place and the program can take advantage of that. Each tile of a certain letter is exactly the same, so by knowing what one of them for a certain screen size looks like, we know what all of them look like, which allows us to check pixel-by-pixel rather than using more advanced image processing techniques.

Solving a Grid

To do this, we will first consider the across words in our grid. This is done by taking each row in turn and determining what tiles can be placed there, if any. If a tile is already present, then it is certain we should leave that there, otherwise we work out what tiles will continue to make a valid word if placed on the grid in that square. This is possible as our dictionary is stored in a trie.

A trie is a tree with letters as edges. Our root is the empty word, and words are constructed by branching out from the root. For example, in our image below, inn can be found by going to i, then in, then inn.

Trie Example (source: Public Domain from Wikipedia)

In my solver, each root also has a flag stating whether this forms a complete word or not. Leaves are automatically complete words, however, we also have words such as "in" (which has "inn" as a child but is still a complete word). This trie structure allows us to work out whether we have a valid part of a word - if that node exists in the trie, completed or otherwise, it can be completed.

The actual algorithm is broken up into two steps. First we look through every square of the grid and mark it with tiles that could be there based on the tiles currently placed on the grid above and below that square. This is because we might end up creating new vertical words as we make horizontal ones, but these words must be complete and legal so only certain tiles can be placed.

Then to find the words, we go through each line. Start at a square, place one of the possibles in it (either a tile already on the board, otherwise one of the tiles we worked out from the previous step that could be played), then make a recursive call with the remaining tiles and new board state. Keep doing this, and whenever you score a word, add it to your word list. Once all the possibilities have been exhausted, score the words in your word list, and return the one with the highest score.

To do the same with down words, we simply flip the grid along the diagonal and repeat the above.

Hints and the Final Email

We then construct the final email using our two solutions (one for the normal dictionary, one for the most common words). This consists of two hints and the solutions separated out using a large amount of whitespace so that on a phone you have to scroll down. This means that users will only ever see the first hint unless they scroll down for more. These are constructed simply from the data in the solutions given - the first hint looks at the coordinates of the middle of the word to find the quadrant and attached word, and looks at the word itself for the second hint.

Finally, this email is sent off.

URL: https://github.com/finnbar/wwfsolver