Creating an Online Boggle Solver :: Solving the PuzzleBy Scott Mitchell
My family enjoys playing games and one of our favorites is Boggle, an addictive word game where players attempt to find as many words in a 4x4 grid of letters. At the end of a game, players are left wondering whether there were any unearthed words. To answer this question once and for all, I created an online Boggle solver using ASP.NET version 3.5.
This article is the second installment in a two-part series. Last week's article, Building
the User Interface, examined the Boggle solver web page's user interface, which consists of 16 TextBox Web controls arranged in a 4x4 grid and three
Button Web controls for solving the user-entered puzzle, solving a randomly-generated puzzle, and clearing the board. A ListView control is used to display
the solutions in a three-column HTML
This second and final installment details the code used to solve the puzzle. Solving the puzzle requires having a dictionary of legal words and objects that mirror the structure and functionality of the board and of solutions. These objects are implemented as classes that include internal data structures that use a number of features in the .NET Framework, including: Generics; automatic properties; and caching. The complete source code is available for download at the end of the article.
Try out the live demo or read on to learn more!
|Have You Read Building the User Interface Yet?|
|If you have not yet read the first installment of this two-part series, Building the User Interface, please do so before tackling this article. The Building the User Interface article includes information about the rules of Boggle, design decisions, and other important topics.|
Maintaining a Dictionary of Legal Words
For the Boggle solver to determine what combinations of letters constitute valid solutions it needs to maintain a dictionary of legal words. The dictionary used by the Boggle solver is implemented as a class named
BoggleDictionaryclass is used by the Boggle solver in the following way: for each new combinations of letters, the solver asks the
BoggleDictionary, "Is this combination of letters a legal word?" For example, consider the following Boggle board:
The solver will try various legal combinations of letters, like "fari", "farh", "fars", and "farm". With each of these combinations, it asks ther e i b t m f w i r a e r h s t
BoggleDictionary, "Is this combination of letters valid?" The
BoggleDictionary, then, would reply in the affirmative for "farm" and in the negative for "fari", "farh", and "fars". Furthermore, the Boggle solver needs to ascertain from the
BoggleDictionarywhether it makes sense to keep probing for additional letters. For example, the letters "irat" is not a valid word, but if the Boggle solver gives up at this point it won't find the word "irate". However, the Boggle solver should not foolishly chase word combinations that have no hope of reaching a solution. That is, the letters "hrir" is not a valid word, nor are there any legal words that start with "hrir", so there's no need to keep probing for more solutions.
One of the challenges in implementing
BoggleDictionary is to ensure that the words in the dictionary can be efficiently searched in the manner
by which the Boggle solver requires. Because the dictionary will be very large (tens of thousands of words, for instance) and because there are many different
ways for the solver to combine the tiles on the board, the efficiency with which the dictionary can be searched will dramatically impact the overall
performance of the puzzle solver.
In the end, I had the
BoggleDictionary use a
Dictionary object with the first n letters of each valid word combination
used as the key, where n is the minimum number of characters that must appear in a word for it to be considered a solution. (According to the official
rules, any word with three or more letters is valid; I typically only count four-letter words as valid.) Each
Dictionary key points to a list of
words that start with the letters.
Dictionary structure is illustrated by the figure below, which shows a subset of the
Dictionary keys and their corresponding
values. The picture below shows the
Dictionary structure when searching for four-letter words. It depicts three keys: "fata", "fate", and
"fath". Each key's value is a list of strings that start with the same value as the key. For example, the key "fata" has a list of strings as its value
that includes words like "fatal", "fatally", "fatalistic", and others.
|Background on the |
If you are not familiar with the |
Now that we've decided how to model the words in the
BoggleDictionary class, we need to determine the allowable words that will populate
Dictionary structure. There are many websites that offer lists of English words in the form of a text file. I already had
such a file on my computer from a previous project that lists words by the letters they contain, ordered alphabetically. Specifically, on each line
the text file contains an entry of the following form:
|alphabetical list of letters constituting the words|word1|word2|...|wordN|
For example, the words "polyps" and "sloppy" contain the same combination of letters: one "o"; one "l"; two "p"s; and one "s". These letters, when arranged alphabetically, are "loppsy"; consequently, the following entry exists in the dictionary text file:
The dictionary text file is read in and its words are populated into the
Dictionary object in the
Load method. The
Load method accepts a single string input parameter, dictionaryPath, which specifies the full phsyical
path to the dictionary file. (Note that the
Load method is marked as
private; it's not meant to be called from outside the
class. Rather, it's called from the
Load method starts by reading in the lines of the dictionaryPath text file into the
entries string array. It then
loops through each string in the array, splitting the line by the pipe character (
|), which is what delimits each word. These "pieces" are loaded
words string array using the
Recall that the first entry on each line is the alphabetical arrangement of letters in the remaining words on the same line. Therefore, we don't want
to process this first entry, only the subsequent ones. Hence, the loop that walks through the elements of the
words starts at index 1
(instead of 0). For each word in
words whose length is greater than or equal to
index_size (which is the minimum number of
letters needed in a word to be considered a solution) and less than or equal to
max_word_size (which is the total number of tiles on the
board and, therefore, the maximum length of any solution), then the item is added to the
Before adding the word to the
Dictionary object we must first make sure that the
Dictionary object (
DictTable) contains an appropriate key.
For example, when adding the word "fatal", we must ensure that the
Dictionary object has the key "fata". This is handled by the
ContainsKey. If the key does not exist, the
Dictionary object entry is added; otherwise, if it already exists, the
list of string is referenced. In the end, the key is created (if needed) and the word is added to the
Caching the Dictionary
Every time a user solves a Boggle board, the solver must first load the dictionary. However, the dictionary information is likely to change infrequently, if at all. It is a prime candidate for caching. As discussed in .NET Data Caching and Caching with ASP.NET, ASP.NET offers a rich and robust API for caching objects in memory.
BoggleDictionary includes a
GetFromCache method that looks for a
BoggleDictionary instance in the .NET data cache.
If it is not found, a new instance of the class is created and stored in the cache.
BoggleDictionary object is not found in the cache, it is inserted back into the cache via the call to
which includes a cache depedency. A cache dependency is a mechanism by which to instruct the cache to evict an item if a dependent object is changed.
In this case, we instruct the data cache to automatically remove the
BoggleDictionary instance from the cache whenever the specified
dictionary text file (dictionaryPath) is modified. That means that the cached
BoggleDictionary object will automatically be
"refreshed" if you modify the dictionary text file (such as by adding or removing words).
During the puzzle solving process, every time a solution is found it needs to be remembered so that it may later be displayed in the web page. (It must also be remembered so that identical solutions are not returned. That is, with many board arrangements there are more than one way to find the same solution. We do not want to include these duplicates in the output.)
The solutions are modeled via the
BoggleWord class, which has two properties:
Word- the actual solution
Score- the score for the solution. The score is based on the length of the words and is spelled out in the official Boggle rules.
Wordproperty demonstrates a new new feature of C# 3.0: automatic properties. Oftentimes, classes include very simple property statements that return and set a private member variable without performing any special logic or validation in the getter or setter. These simplistic properties have the following pattern:
These types of properties can now be condensed into a much more terse syntax:
Or, if you prefer an uber-terse syntax:
Behind the scenes, the compiler automatically adds the private member variable and flushes out the getter and setter. For more on automatic properties, see C# 3.0 Features: Automatic Properties.
BoggleWord class has two methods used in dispaying the solutions in the web page:
ToString- returns the solution in the format, "word (x points)", where word is the solution and x is the number of points for the solution.
CompareTo- used to sort the results alphabetically.
BoggleWordListclass that holds a collection of
BoggleWordListclass also has a
TotalScoreproperty that returns the sum of its
BoggleBoard - the Puzzle Solving Workhorse
BoggleBoardrepresents a particular Boggle board configuration. We examined this class in the Building the User Interface article. Recall that the web page that collects the user's input solves the puzzle by first creating a
BoggleBoardinstance based on the values entered by the user in the 16 TextBox controls and then calling the
Solvemethod returns a
BoggleWordListthat contains the solutions for the board (if any).
Solve method starts by retrieving the
BoggleDictionary object in the data cache by calling
BoggleDictionary.GetFromCache. It then loops through the 16 tiles in the board and, for each tile, calls the
method, which finds solutions starting from the specified position and branching outwards recursively.
SolvePuzzle method accepts as inputs:
BoggleDictionaryobject to use to determine whether a particular combination of letters is a valid word, and whether to keep searching.
- The set of current solutions
- The row and column position to use to get the next letter
- The current combination of letters being constructed
SolvePuzzlemethod starts by asking the
BoggleDictionaryobject whether it's worthwhile to keep on searching given the current combination of letters. The
KeepGoingmethod, which we won't examine in detail, returns a Boolean value indicating whether there are any words starting with the passed-in combination of letters. In a nutshell, the
KeepGoingmethod always returns
trueif the length of the passed-in string is less than the number of letters that make up the
Dictionaryobject's key. If the passed-in string is long enough, it actually looks up the combination in the
Dictionaryobject to determine whether it makes sense for the solver to continue probing.
KeepGoing method gives us a thumbs up, we then take the value at
and tack it onto the existing combination of letters being tested. If the new combination of letters contains at least as many letters as are needed
for a valid solution, the
Contains method is called to see if the solution is valid. If it is - and if
the solution has not already been found, it's added to the list of solutions.
The next step is the most important: attempting to form new combinations with neighboring tiles. In short, we want to try to form new combinations with
every one of the current tile's neighbors. This is accomplished with two loops to check all positions immediately adjacent to the current tile.
A conditional statement is used to ensure that the neighbor being considered is within the board of play and that it has not already been used in this
exploration. (According to Boggle's rules you cannot use a particular tile more than once when forming a solution.) Used tiles are marked by a tilde
If the neighbor is valid - it's on the board of play and has not already been used in this particular solution attempt - then the
method is called, passing in the new position and new combination of letters.
And that's all there is to it! The entire
SolvePuzzle method is a mere 29 lines of code (including whitespace and comments).
This simplicity is possible thanks to the power of recursion.
In this article and the previous one we looked at building an online Boggle solver using ASP.NET version 3.5. The Boggle solver uses many interesting .NET Framework features to accomplish its goal. The
BoggleDictionaryuses Generics to create a strongly-typed
Dictionarydata structure for efficiently storing and querying the dictionary; the
BoggleWordclass demonstrates the use of automatic properties; and ASP.NET's data cache is used to cache a
BoggleDictionaryinstance in memory so that it does not need to be recreated from the ground up every time the solver is used.
The complete code for this application is available for download at the end of this article. I also invite you to try out a live demo.
UPDATE: I have updated the Boggle solver's user interface to include an Ajax-enabled version! Read more about it at Updating My Online Boggle Solver Using jQuery Templates and WCF.