IS 520: Final Project – Complete Boggle Solution by Trie Structure

Executive Summary

Solving the Boggle puzzle can be fun, but it will be nearly impossible to find all words from any given Boggle board. This program takes any 5x5 Boggle board and returns all valid solution words, the total number of words found, and the total number of words of length four or greater.

The valid Scrabble Words dictionary and the 10,000 most commonly searched words on Google were used to create a dictionary of valid words. The words were loaded into a data structure called a trie which allows for extremely quick computation as the board is completely solved. The trie will stop the search as a possible word becomes invalid. This means that the program does not need to search every possible combination of paths beginning with every letter on the board.

In addition to a complete solution, the program allows the user to input words which are then checked for validity – both validity of the English language and validity for the given Boggle board.

Instructions

Place the .xlsm and the two .txt files in the same directory. Open the .xlsm document and click the “Build Trie” button. After the trie has finished running (can take 0–2 minutes), the “Solve Boggle” and the “User Submit” functions can be run by clicking those buttons. In order to run the “Verify Words” function, the “Solve Boggle” must have been previously run. To reset the board, click the “Clear Words” button. The Boggle board can be reset to various combinations of letters by clicking the “Shuffle Tab” button.

Final Write up

Excel File

Sowpods Dictionary

Google 10,000 Words Dictionary