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

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.