Boggle solver
Boggle is a simple game where players try to form words with adjacent letters. The grid of letters is jumbled randomly before beginning play. I set out on a quest to write a fast Boggle solver that can enumerate all solutions and sort them by length.
Details
The algorithm is actually quite simple thanks to a powerful data structure known as a directed acyclic word graph (DAWG). A DAWG represents a list of words in graph form, with common prefixes sharing common paths through the graph. This data structure allows lightning-fast lookups of words in such a way that fits Boggle's gameplay perfectly. I extended the program to support wildcards as well.
Visualization
Arbitrary-size grids are supported:
The top row of letters are wildcard squares, visualized as red letters during solution visualization:
The program is shockingly fast even when there are a large number of wildcard squares:
Experimenting with solution visualization techniques:
Special multi-letter tiles are supported as well, such as "Qu":
