Scrabble word finder with wildcards

Question

I’ve got a problem and it seems some before me have had similar problems but I haven’t been able to find a working solution for me.

I’m currently building a mobile web application using C#, MySQL, HTML5 and Javascript. The application will be used to help users to find possible words to play while playing games like Scrabble.

The problem I’ve got: How do I get the right words from a MySQL database containing a dictionary from user letter input?

More details: - Users can input any number of letters and also use wildcards (representing any letter) . - If the user inputs “TEST” the result can’t contain words with more than 1 E and S and words with more than 2 T, a result with “TESTER” in it would be bad. - The result can’t contain words with more letters than inputted.

UPDATE: Seems Trie is the solution to my problem as suggested by Eric Lippert here.
Problem is I'm a beginner with both C# and MySQL, so here are some follow up questions:

1. How do I create a Trie from my MySQL dictionary? (400k+ words)
2. How do I store the Trie for quick and future access?
3. How do I access the Trie and extract words from it with C#?

Thank you very much for the help!

Answer 1

How do I get the right words from a MySQL database containing a dictionary from user letter input?

You don't. A relational database table is not a suitable data structure for solving this problem as efficiently as you need to.

What you do instead is you build a trie data structure out of the dictionary (or, if you're really buff, you build a dawg -- a directed acyclic word graph -- which is a sort of compressed trie.)

Once you have a trie/dawg it becomes very inexpensive to test every word in the dictionary against a given rack, because you can "prune out" whole huge branches of the dictionary that the rack cannot possibly match.

Let's look at a small example. Suppose you have the dictionary "OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS" From that you build this trie: (Nodes with a $ are those that are marked as "word can end here".

           ^root^
           /  |  \
         O    P    S
         |    |   / \
         P$   O  O   T   
        / \   |  |   |
       T$  S$ T$ P$  O
       |      |  |   |
       S$     S$ S$  P$
                     |
                     S$

and you have the rack "OPS" -- what do you do?

First you say "can I go down the O branch?" Yes, you can. So now the problem is matching "PS" against the O branch. Can you go down the P subbranch? Yes. Does it have an end-of-word marker? Yes, so OP is a match. Now the problem is matching "S" against the OP branch. Can you go down the T branch? No. Can you go down the S branch? Yes. Now you have the empty rack and you have to match it against the OPS branch. Does it have an end-of-word marker? Yes! So OPS matches also. Now backtrack up to the root.

Can you go down the P branch? Yes. Now the problem is to match OS against the P branch. Go down the PO branch and match S -- that fails. Backtrack to the root.

And again, you see how this goes. Eventually we go down the SOP branch and find an end-of-word on SOP, so "SOP" matches this rack. We don't go down the ST branch because we don't have a T.

We've tried every possible word in the dictionary and discovered that OP, OPS and SOP all match. But we never had to investigate OPTS, POTS, STOP or STOPS because we didn't have a T.

You see how this data structure makes it very efficient? Once you have determined that you do not have the letters on the rack to make the beginning of a word, you don't have to investigate any dictionary words that start with that beginning. If you have PO but no T, you don't have to investigate POTSHERD or POTATO or POTASH or POTLATCH or POTABLE; all those expensive and fruitless searches go away very quickly.

Adapting the system to deal with "wild" tiles is pretty straightforward; if you have OPS?, then just run the search algorithm 26 times, on OPSA, OPSB, OPSC... It should be fast enough that doing it 26 times is cheap (or doing it 26 x 26 times if you have two blanks.)

This is the basic algorithm that professional Scrabble AI programs use, though of course they also have to deal with things like board position, rack management and so on, which complicate the algorithms somewhat. This simple version of the algorithm will be plenty fast enough to generate all the possible words on a rack.

Don't forget that of course you only have to compute the trie/dawg once if the dictionary is not changing over time. It can be time-consuming to build the trie out of the dictionary, so you might want to do so once and then figure out some way to store the trie on disk in a form that is amenable to rebuilding it quickly from disk.

You can optimize the memory usage by building a DAWG out of the trie. Notice how there is a lot of repetition because in English, lots of words end the same, just as lots of words begin the same. The trie does a great job of sharing nodes at the beginning but a lousy job of sharing them at the end. You can notice for example that the "S$ with no children" pattern is extremely common, and turn the trie into:

           ^root^
          / |  \
        O   P    S
        |   |   / \
        P$  O  O   T   
       /  \ |  |   |
      T$  | T$ P$  O
      |    \ | |   |
       \    \| /   P$
        \    |/    |
         \   |    /
          \  |   /  
           \ |  /
            \| /  
             |/
             |       
             S$

Saving a whole pile of nodes. And then you might notice that two words now end in O-P$-S$, and two words end in T$-S$, so you can compress it further to:

           ^root^
           / | \
          O  P  S
          |  | / \
          P$ O \  T   
         /  \|  \ |
         |   |   \|
         |   |    O
         |   T$   |
          \  |    P$
           \ |   /
            \|  /  
             | /
             |/   
             S$

And now we have the minimal DAWG for this dictionary.

Further reading:

http://dl.acm.org/citation.cfm?id=42420

http://archive.msdn.microsoft.com/dawg1

http://www.gtoal.com/wordgames/scrabble.html