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 about missed words. 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 created a Boggle solver web application (back in 2008) that prompts a user for the letters in the Boggle board and then recursively explores the board to locate (and display) all available solutions. This Boggle solver is available online - fuzzylogicinc.net/Boggle. My family uses it every time we get together and play Boggle. For more information on how it works and to get your hands on the code, check out my article, Creating an Online Boggle Solver. In November 2010, I updated the code to make it more Ajax-friendly; see Updating My Online Boggle Solver Using jQuery Templates and WCF for details.
While playing a game of Boggle I found myself wondering how many total available words are present in a typical game of Boggle, and how many total points are available. It soon dawned on me that I could answer this question using my Boggle solver application and a the Monte Carlo method. My Boggle solving engine has a GenerateBoard method that randomly assembles a legal Boggle board. By generating tens of thousands of random Boggle boards, running them through my solver, and recording the number of words and total points available I could arrive at a good approximation for the average number of words and points in a given game of Boggle. (Scroll to the bottom of this blog entry if all you care about is the average number of words and points per game.)
I started by creating a new class in my Boggle solving Class Library, which I named GameLogger. This class has a single method, LogGame, which takes an inputs the BoggleBoard object that was used to find the solutions and the BoggleWorldList object that comprises the set of solutions to the accompanying BoggleBoard. This method then inserts a record into a database table (boggle_Boards) that logs:
- The BoardID, which is a 16-character string that uniquely identifies the board. Namely, it contains one character for each letter in the board.
- The NumberOfSolutions, which is the number of words on the for the board.
- The Score, which is the cummulative score of all of the words on the board. In Boggle, 3 and 4 letter words score 1 point, 5 letter words score 2, six letter words score 3, seven letter words score 5 and words eight letters or longer score 11.
- The MinimumWordLength, which specifies the minimum number of letters needed to form a valid solution. Boggle’s rules permit words three or more letters in length, but my family often plays a variation that permits only four letter or longer words.
The code for my Monte Carlo simulator is brain-dead simple – create a new Boggle game, solve it, then log it, and do this until I tell you to stop.
var gt = GameTiles.OfficialBoggleGameTiles();
var board = new BoggleBoard(3, gt.GenerateBoard());
var solutions = board.Solve();
Let the above code run for 5 minutes and you’ve got tens of thousands of solved, random Boggle boards in the database from which you can now ascertain average number of words and score.
The following query returns the average number of solutions and score for games allowing words with 3 of more letters:
SELECT AVG(CAST(NumberOfSolutions AS decimal)), AVG(CAST(Score AS decimal))
WHERE MinimumWordLength = 3
Which comes out to:
Average # of words: 66.82
Average score: 93.25
If we compute the average number of words and points for games requiring four or more letters we get, expectedly, lower results. For such games you can expect, on average, 42.12 words and 68.30 points.
So, next time you break out Boggle, keep in mind that, on average, there are nearly 67 words hiding there, ready for you to find. And after time expires, be sure to use my Boggle solver to see all the words that were present!
Note: Of course, these results are based on the dictionary that my Boggle solver uses. My dictionary may permit or deny certain words that you deny or allow, in which case these averages would be skewed. Unfortunately, I am unaware of where I got my dictionary file. I downloaded it from some website many years ago. I know many word-based games use the Enhanced North American Benchmark Lexicon as their dictionary. I am not using this but would like to integrate it at some point in the future…
Republished from Scott On Writing.NET [3 clicks].
Read the original version here [0 clicks].