Creating an Online Boggle Solver :: Building the User Interface

By Scott Mitchell

Creating an Online Boggle Solver

This article is one in a two-part series on creating an online Boggle solver using ASP.NET version 3.5.

Building the User Interface - discusses what Boggle is, the rules of the game, and the design decisions made when planning the application. Shows how the user interface was constructed and how it has been enhanced through the use of client-side script.

Solving the Puzzle - dissects the classes, logic, and workflow used to solve the Boggle puzzle.

Introduction

I spend most of my day writing about ASP.NET or building ASP.NET applications for clients. As every ASP.NET developer knows, the bulk of ASP.NET development centers around data access - building pages to collect user input and crafting reports to summarize that information. To help break this monotony, I occasionally set aside an afternoon to work on a more interesting project, which helps rechage my batteries. I've shared such fun programming projects in past articles here on 4Guys (see Creating a Quick and Dirty Online Blackjack Game).

My immediate and extended family enjoys playing games, and one of the favorites is Boggle. Boggle is a word game trademarked by Parker Brothers and Hasbro that involves several players trying to find as many words as they can in a 4x4 grid of letters. At the end of the game, players compare the words they found. During this comparison I've always wondered what words we may have missed. Was there some elusive 10-letter word that no one unearthed? Did we only discover 25 solutions when there were 200 or more?

To answer these questions, I decided to create a Boggle solver and did so using ASP.NET version 3.5. The Boggle solver recursively explores the board and locates (and displays) all available solutions. With this nifty little web page, at the conclusion of each Boggle game we can see what words we missed.

This article is the first in a two-part series that details the application, its design, and some of the challenges faced when creating it. In this first installment we will look at the user interface; the second installment examines the logic used to actually solve the puzzle. The complete source code for the Boggle solving application is available at the end of the article. You can also see a live demo in action at www.FuzzyLogicInc.net/Boggle. Read on to learn more about this fun little project.

- continued -

The Rules of Boggle

Before we examine the code, I should first take a moment to explain the rules of Boggle. Boggle is a word game consisting of 16 dice with letters on each face. The dice are jumbled and randomly fall into 16 slots in a 4x4 grid. At that point, a three minute timer is set and all players write down as many words as they can before the timer expires. The letters of a word are formed by starting at any letter then moving, horizontally, diagonally, or vertically to neighboring dice; each tile may be used at most once per word formed. At the end of the three minutes, players enumerate their solutions and any common words are crossed off. Each player sums up his remaining words, awarding himself 1 point for 3 or 4 letter words, 2 points for 5 letter words, 3 points for 6 letter words, 5 points for 7 letter words, and 11 points for words 8 letters or longer.

Prompting the User for the Boggle Board Layout

A user visiting the page must be able to enter the letters from her Boggle board in order to see the complete solutions list. To accomplish this, I used an HTML <table> to generate a 4x4 grid. I then placed a TextBox Web control in each cell and set the TextBox's with to 30px (via CSS). I named the 16 TextBoxes cXY, where X is their row position (0..3) and Y is their column position (0..3). For example, the TextBox in the upper left was named c00, the one in the upper right corner c03, and the one in the bottom right corner c33.

The following declarative markup illusrates this naming convention.

In addition to the 16 TextBox controls, the page contains three Button Web controls that the user may click to solve the currently entered board, generate a random board, or clear the board. There's also a DropDownList control from which the user can choose the minimum number of letters each solution must contain. The rules of Boggle require all words must be at least 3 letters long; my family usually plays with a 4 letter word minimum. The DropDownList has the hard coded values 3, 4, 5, and 6.

I augmented these 16 TextBoxes with a bit of client-side JavaScript to simplify and hasten the process in entering the Boggle board's layout. In particular, I added two client-side event handlers:

onfocus - this event occurs whenever focus is moved to the TextBox (such as tabbing into it). For this event, I called the select() method, which selects the text in the textbox (if any). The net effect is that if a user tabs into a textbox that has an existing letter, they do not have to delete the old letter by clicking Delete. Since it's selected, by entering the new letter the old one will be deleted.
onkeyup - this event fires after the user presses a key when focus is in the textbox. After entering a letter, I wanted the focus to immediately shift to the next TextBox so that the user could enter the board's layout by typing in the 16 letters (rather than having to type one letter, then hit Tab, then another letter, then hit Tab, and so on). The one gotcha here was that I had to be careful to only advance to the next textbox if the user typed in a letter. If they hit the Delete key, for instance, I would wanted to leave them in the textbox.

This JavaScript was added via the TextBox's Attributes collection. In the Page_Load event handler I enumerated the rows and columns and, for each TextBox, added the client-side event handlers. For the onkeyup event I needed to determine the ClientID of each TextBox control as well as the ClientID of the TextBox to send the user to after they had entered a letter. After the user entered a value for the last textbox, focus is moved to the SolvePuzzle button.

protected void Page_Load(object sender, EventArgs e) { for (int rowPos = 0; rowPos < BoggleBoard.ROWS; rowPos++) for (int colPos = 0; colPos < BoggleBoard.COLS; colPos++) { TextBox cMe = c01.Parent.FindControl(string.Concat("c", rowPos, colPos)) as TextBox; int moveToRowPos = rowPos; int moveToColPos = colPos + 1; if (moveToColPos >= BoggleBoard.COLS) { moveToRowPos += 1; moveToColPos = 0; } WebControl cMoveTo = null; if (moveToRowPos < BoggleBoard.ROWS) cMoveTo = c01.Parent.FindControl(string.Concat("c", moveToRowPos, moveToColPos)) as WebControl; else cMoveTo = SolvePuzzle; if (cMe != null) { cMe.Attributes["onkeyup"] = string.Format("moveTo('{0}', event);", cMoveTo.ClientID); cMe.Attributes["onfocus"] = "this.select();"; } } ... }

The client-side script functionality is added in the lines that start with cMe.Attributes["eventName"]. For example, the onkeyup event is assigned to the string moveTo('moveToID', event);. The moveTo JavaScript function is defined in the Script.js file. It determines whether a letter key was pressed and, if so, it sets focus to the element whose ID matches the moveToID.

function moveTo(id, e) { var k; // Determine what key was pressed if (window.event) // IE k = e.keyCode; else if (e.which) // Netscape/Firefox/Opera k = e.which; // Only advance if a letter was pressed if (k >= 65 && k <= 90) { var ctrl = document.getElementById(id); if (ctrl) ctrl.focus(); } }

For more information on emitting JavaScript from an ASP.NET page, see Working with Client-Side Script.

Validating the Board

After the user has spelled out the layout of the board, but before our program starts its hunt for solutions, we need to ensure that the board specified by the user is valid. Each TextBox in the Boggle board must contain precisely one letter. This verification - along with the actual solving of the puzzle - is handled by a class I named BoggleBoard. This class's constructor accepts as input the minimum length of a valid word along with the 16 letters that make up the board. The BoggleBoard class also has an IsValid() method that returns a Boolean indicating if the board is valid. If it is not, the ErrorMessage property contains a list of strings with a description for each problem cell.

After the user enters the board's layout and clicks the "Solve Puzzle" button, the following code executes:

protected void SolvePuzzle_Click(object sender, EventArgs e) { // Create the BoggleBoard BoggleBoard bb = new BoggleBoard( Convert.ToInt32(MinWordLength.SelectedValue), c00.Text.Trim(), c01.Text.Trim(), c02.Text.Trim(), c03.Text.Trim(), c10.Text.Trim(), c11.Text.Trim(), c12.Text.Trim(), c13.Text.Trim(), c20.Text.Trim(), c21.Text.Trim(), c22.Text.Trim(), c23.Text.Trim(), c30.Text.Trim(), c31.Text.Trim(), c32.Text.Trim(), c33.Text.Trim() ); // Ensure that the board is valid if (!bb.IsValid()) { // Invalid board, display message base.DisplayAlert(string.Format(@"There were problems parsing the Bobble board you entered:\n\n{0}\n\nPlease fix these errors and try again.", bb.ErrorMessage)); } else Response.Redirect("EnterBoard.aspx?BoardID=" + bb.BoardID + "&Length=" + MinWordLength.SelectedValue); }

If the board is invalid, the ErrorMessage property is displayed through a call to DisplayAlert, which is a custom method in a base page class that displays a JavaScript alert box. (For more information on using a base page class, see Using a Custom Base Page Class for Your ASP.NET Pages' Code-Behind Classes; for more on JavaScript's messagebox features, see Adding Client-Side Message Boxes in Your ASP.NET Web Pages.)

If the board is valid, the user is redirected back to the same page (EnterBoard.aspx), but the querystring includes the board's ID and the minimum length of each word. Rather than use the standard postback model, I decided to have my actions be querystring based so that a user could bookmark or email the URL of a particularly interesting Boggle board. (This interest came upon a Boggle board I encountered where there were over 250 solutions of 4+ letter words!) The BoggleBoard class's BoardID property returns a string of the board's letters, from the top left down to the bottom right. If the querystring includes a BoardID value, the Page_Load event handler populates the 16 TextBoxes with the corresponding values and then solves the puzzle.

protected void Page_Load(object sender, EventArgs e) { ... if (!Page.IsPostBack) { c00.Focus(); // Set the value for the DropDownList if (!string.IsNullOrEmpty(Request.QueryString["Length"])) { ListItem li = MinWordLength.Items.FindByValue(Request.QueryString["Length"]); if (li != null) li.Selected = true; } if (!string.IsNullOrEmpty(Request.QueryString["BoardID"]) && Request.QueryString["BoardID"].Length == 16) { // Set the values for the 16 TextBoxes c00.Text = Request.QueryString["BoardID"][0].ToString(); c01.Text = Request.QueryString["BoardID"][1].ToString(); ... Some assignment statements removed for brevity ... c32.Text = Request.QueryString["BoardID"][14].ToString(); c33.Text = Request.QueryString["BoardID"][15].ToString(); // Solve the puzzle Solve(); } } }

The Solve() method called from the Page_Load event handler is a method defined in the code-behind class and is shown below. It creates a BoggleBoard instance, poopulates it with the values in the 16 TextBoxes, and calls the BoggleBoard class's Solve() method, which does all the heavy lifting in discovering the solutions. The BoggleBoard class's Solve() method returns a BoggleWordList object, which contains a list of solutions and their scores. If there is at least one solution, the number of solutions and the total score is displayed in the SolutionsMessage Label and the set of solutions are displayed in the WordList ListView control. If no solutions were found, the message "There were no solutions found" is displayed instead.

private void Solve() { // Create the BoggleBoard BoggleBoard bb = new BoggleBoard( Convert.ToInt32(MinWordLength.SelectedValue), c00.Text.Trim(), ..., c33.Text.Trim() ); // Solve the Boggle board BoggleWordList words = bb.Solve(); // Display the list of words Results.Visible = true; if (words.Count > 0) { SolutionsMessage.Text = string.Format("The following <b>{0}</b> solutions exist for a total of <b>{1}</b> points:", words.Count, words.TotalScore); WordList.DataSource = words; WordList.DataBind(); WordList.Visible = true; } else { SolutionsMessage.Text = "There were no solutions found!"; WordList.Visible = false; } }

The WordList ListView renders a three-column HTML <table>, placing the contents of each solution in a cell.

<asp:ListView ID="WordList" runat="server" GroupItemCount="3"> <LayoutTemplate> <table border="0" style="width:95%;text-align:center;"> <asp:PlaceHolder runat="server" ID="groupPlaceholder"></asp:PlaceHolder> </table> </LayoutTemplate> <GroupTemplate> <tr> <asp:PlaceHolder runat="server" ID="itemPlaceholder"></asp:PlaceHolder> </tr> </GroupTemplate> <ItemTemplate> <%# DisplayTableCell(Container.DataItem as BoggleWord) %> </ItemTemplate> </asp:ListView>

As you can see, the ListView's ItemTemplate calls a helper method to generate its markup. The helper method is located in the code-behind class and DisplayTableCell; it is passed a BoggleWord object and returns the HTML to render. (This technique has been available since the first version of ASP.NET; for a primer on this technique, see Customizing the Appearance of a DataGrid Column Value.) The DisplayTableCell method returns table cell markup (<td>) with the word and score present. The word is displayed as a hyperlink pointing to the dictionary.com entry and the table cell is assigned to one of the following CSS classes based on the word's score: Score1, Score2, Score3, Score5, Score11. The different CSS classes impose different formatting rules. Score2, for example, formats the table cell using a light yellow background color; Score11 formats the cell with a pink background color and bolds the cell's text.

protected string DisplayTableCell(BoggleWord bw) { return string.Format(@"<td class=""Score{0}""><a href=""http://dictionary.reference.com/search?q={1}&db=luna"">{1}</a> ({0} {2})</td>", bw.Score, bw.Word, bw.Score > 1 ? "pts" : "pt"); }

For more information on the ListView control, consult Using ASP.NET 3.5's ListView and DataPager Controls.

Looking Forward

At this point we have examined the Boggle solver's user interface. To recap, the user interface consists of a 4x4 grid of 16 TextBox Web controls, three Button Web controls, a DropDownList, a Label, and a ListView control. After entering a board and clicking the "Solve Puzzle" button, the page creates a BoggleBoard class instance and calls its Solve() method (assuming the user's inputs were valid). The Solve() method returns a BoggleWordList object that contains the set of solutions; these are then displayed in a ListView control.

In the next and final installment we will examine how the BoggleBoard class finds the solutions. In the interim, feel free to try out the Boggle solver live demo. The complete source code is available at the end of the article.

Happy Programming!

By Scott Mitchell

Further Readings:

Boggle Wikipedia Entry

Working with Client-Side Script

Using ASP.NET 3.5's ListView and DataPager Controls

Creating an Online Boggle Solver :: Solving the Puzzle

Attachments

Download the Demo (in ZIP format)

Live Demo