Scrabble solver

Details

The GADDAG data structure is actually quite similar to the DAWG (see my Boggle solver for more details). Similar to the DAWG, all of the words of the dictionary are represented in graph form. Unlike the DAWG, each word is inserted n times, where n is the length of the word. For example, the word "hello" is inserted five times:

1. H$ELLO
2. EH$LLO
3. LEH$LO
4. LLEH$O
5. OLLEH$

As an example, consider a board that contains the word "HE". We start at the right/bottom boundary of the word on the board and perform a lookup in the GADDAG. So, we enter the GADDAG with the letter "E". We find "EH$LLO" as a potential candidate, so we move left/up one position on the board while simultaneously moving forward one letter in the candidate, which takes us to "H". The candidate is still a potential match. We then encounter a special $ symbol in the candidate, which indicates to stop moving left/up on the board and skip to the end of the word on the board and move right/down to continue matching letters. If a mismatch occurs at any point between the board and candidate, then we ignore this candidate and move to the next. If we encounter a blank spot on the board, then we consult the rack to see if any letters can be applied. If not, the candidate is ignored.

Stated another way, the GADDAG is really just a DAWG that contains every dictionary word at every possible entry point into that word. The $ is a special indicator that means "flip sides and direction" while matching on the board.

Visualization

I like to start simple and gradually refine:

I enhanced the legibility of the board/tiles, rack and score. The candidates are scored and sorted by score. The active candidate word is shown in red:

GADDAG match: DEWELS$

I implemented a special screen that shows how many of each tile are still available:

Arbitrary tile modifiers are supported. I also implemented GADDAG traversal visualization (notice the blue, yellow and green arrows). The second screenshot contains some nonsense words on the board in order to test the algorithm.

GADDAG match: D$WARFS

GADDAG match: FRAF$ETCHEDNESS

Wildcard tiles are also supported and are visualized as lowercase letters when placed on the board. Note that special care must be taken while traversing and scoring candidates to take incidental words into account (e.g., "ow" and "so" in the first screenshot and "ag", "er" and "aa" in the second screenshot).

GADDAG match: GAH$IOSCOPE

GADDAG match: AHCRA$EAN

I made the tiles 3D and implemented new shading. The candidate solution is shown in blue, and any newly formed incidental words are shown in green:

GADDAG match: SER$ITE

I implemented bump mapping to make the tiles pop and adjusted the lighting and field of view:

The font can be changed easily. I changed wildcard tiles to be visualized with asterisks instead.

Here is a video demonstrating the ability to easily cycle through the candidate solutions: