## Thursday, December 3, 2009

### 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

`astaifuemtndaaos`

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:

 `234936astaifuemtndaaos954amandusdentistdonatistitonamamantodeamistendsituatesituatedstudenttamandutamanduatsunami`

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 positiondef 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.