A GADDAG is a highly specialized form of a trie data structure optimized for time-efficient queries appropriate for crossword-style word games, like the board game Scrabble. The data structure was first described by Steven Gordon in his 1993 paper titled A Faster Scrabble Move Generation Algorithm, which describes the tradeoffs between the GADDAG and its primary competitor, the Directed Acyclic Word Graph (DAWG).

I found the paper early on in my computer science education. Newly introduced to programming and exploring a curiosity in the world of competitive Scrabble, I asked the natural question, “How do computers play Scrabble?”. At the time, I found the paper to be too complicated to follow, and quickly gave up on any idea of trying to implement such a Scrabble playing system.

Nearly 10 years later, I discovered the paper again deep within my carefully organized bookmarks. I decided to implement my own GADDAG library to get a better field for how they worked and they tradeoffs they involved. Rather than focusing on performance, as Gordon’s paper did, my implementation focuses on being accessible to newer programmers and is intended purely as a learning exercise. A number of design decisions notably slow down the implementation making it unsuitable for a competitive environment, such as explicitly tracking step numbers and the “role” each step plays within various algorithms when traversing the graph.

As an example of how the library may be used, I have created a D3.js driven visualization of how the data structure works with various querying algorithms as part of a data visualization class.