Scramble is a word game where players try to find as many words as they can in a 4×4 or 5×5 grid of letters. I’ve been playing this game more than I’d like to admit to so in an attempt to hopefully ween me off the game, I’ve coded a solution in Java which finds every word in the grid.

Setting Up the Problem

I set the problem up using an undirected, unweighted, connected graph.
Here’s my graph implementation using an adjacency list:

Since the same letters can appear multiple times in the grid, I represented each vertex using a Node object rather than simple Strings (letting me override equals()). Here’s the code for the Node class:

The next step is to build the graph representation of the grid. I decided to read the grid from file into a 2d array and use that to create the necessary vertices/edges:

Finding Every Word in the Graph

Now that we have a graph representation of the board, we can find every word using a variant of depth-first search(DFS).

In findWords(), we initialize the visited HashMap which is used to keep track of the vertices we’ve seen on the current path and to prevent the same vertices from being used multiple times for the same word. From there, we call buildWords() with each of the vertices (treating each of the vertices as the root).
buildWords() constructs depth-first trees – Node n is the node we’re currently visiting and String word is the word that we’re constructing. First, we set the node to visited and then we travel down a path. To keep from proceeding down a path with no words, we apply a simple constraint to check that words exist with the letters on the current path. Without the constraint in place, the algorithm can be used to find every unique path in a graph.
Traditionally in DFS, we continually search deeper until a goal vertex is found or until we reach a terminal vertex with no children whilst marking vertices we’ve seen to keep from falling into infinite loops. Taking a coloring approach, we can color unvisited nodes white; visited nodes are colored two ways – gray vertices have some adjacent white vertices whereas all vertices adjacent to black vertices have been visited. By coloring vertices in this way, each vertex is visited at most once.
In our case, we don’t need to differentiate between visited vertices since rather than just traversing the graph to visit each vertex once, we want to potentially traverse every path in the graph. Fortunately for us, doing so requires only a single modification to DFS (asides from using a simpler coloring approach) – we reset the current vertex to not visited once we backtrace which allows for its inclusion in other paths.

The Word List to Test Against

I used JDBC to connect to a mysql database built using the English word list from ispell. I modified the word list by removing words less than 2 characters long and words with non-alphabetical characters. Unfortunately, I don’t know which word list is being used in Scramble and so many of the words found via my code are considered invalid by the game and vice versa.

Conclusion

My solution takes <5 seconds to find all words in a game of Scramble and I'm guessing I could increase the performance by forking off calls to buildWords. Although it's a bit clumsy to use while playing since the games are timed, I managed to come in first a bunch of times while playing online multiplayer - my code has sufficiently sucked the fun out of the game and so hopefully I won't be playing it as much =). Now if only I could code a solution to Paper Toss :p.

All code is available here. Note that a Java properties file (database.properties) is required with the following keys: jdbc.drivers, jdbc.url, jdbc.username, and jdbc.password. The jumble.txt file demonstrates the required format for the puzzle (space between each vertex; newline for each row).