How the letters solver works

The aim of the Countdown letters game is to find words that can be made using some or all of the given letter tiles, without using any tile more than once. Longer words are worth more points.

Example: GYHDNOEUR

We can make the word "dog" because all of "D", "O", and "G" appear, but we can't make the word "good" because there is only one "O".

To find out the words that can be made, we use a word list telling us the set of valid words.

Given a word list, we build a Trie data structure, offline (i.e. only when the word list changes, not on every request).

To solve a letter set, we start at the root of the trie. For each child node whose letter exists in our collection of unused letters, we recurse into that child node with a copy of the letter set but with the consumed tile removed. When we reach a node of the trie that is labelled as the end of a word, we know that the path taken through the trie represents a valid word, and we add that word to our list of valid solutions.

Having found the list of all valid solutions, we sort them by length and display the longest words first. Within a given length we sort the words by a measure of their word frequency so that more common words tend to appear more prominently.

As an optimisation, to save time and memory wasted on making millions of copies of the letter set, we instead maintain a flag for each letter tile that says whether that tile has already been used, and toggle it to true to prevent lower levels of recursion from reusing the same tile, and toggle it back to false once the recursive call returns.