Boggle

I found a fun text problem here, called Boggle. It is even an app for the iPhone. The basic rules are that we have a 4 x 4 matrix containing letters

asta
ifue
mtnd
aaos

Given a puzzle, the object is to form words, starting at any position but using two rules:

• sequential letters must be neighbors (diagonals are OK)
• no position can be used twice

(duplicate letters are valid puzzles, as shown in the example)

To make life simpler, we can use a dictionary of valid words, for example (on my Snow Leopard system):

/usr/share/dict/words

Rather than choose letters for the puzzle equally often, I chose letters at the frequency they occur in the dictionary. Here is one run:

234936 asta ifue mtnd aaos 954 amandus dentist donatist itonama mantodea mistend situate situated student tamandu tamandua tsunami

There are almost 235,000 words in the dictionary. 954 of them pass the first filter (below). We only print words longer than a threshold T = 5.

There are lots of solutions shown, in different languages (link).

My version uses an idea adapted from BLAST. Make a list of all k-words in the table (adjacent letters, k=2), and filter the dictionary against the list. This reduces the search space by about 200- to 1000-fold.

# get k-words (k=2), by position def getKWords(puzzle): L = list() for i in range(16): temp = list() c1 = puzzle[i] for j in near[i]: temp.append(c1 + puzzle[j]) L.append(temp) # convert to simple list kL = list() for eL in L: kL.extend(eL) return list(set(kL))

The second phase tests whether a word is a valid solution to the puzzle by checking its "path." I won't post that, but you can find my full solution here.