Boggle SERSPATGLINESERS solution

gistfile1.txt

#!/usr/bin/python
from collections import defaultdict

board = list("SERSPATGLINESERS".lower())

with open("word.list") as f:
    allowed = set(word.strip().lower() for word in f)

interim = set()
for word in allowed:
    for x in range(len(word)):
        interim.add(word[:x])

found = set()

moves = {
        #corners
        0:[1,4,5],
        3:[2,6,7],
        12:[8,9,13],
        15:[10,11,14],

        #edges
        1:[0,2,4,5,6],
        2:[1,3,5,6,7],
        4:[0,1,5,8,9],
        7:[2,3,6,10,11],
        8:[4,5,9,12,13],
        11:[6,7,10,15,14],
        13:[8,9,10,12,14],
        14:[9,10,11,13,15],

        #middle
        5:[0,1,2,4,6,8,9,10],
        6:[1,2,3,5,7,9,10,11],
        9:[4,5,6,8,10,12,13,14],
        10:[5,6,7,9,11,13,14,15]
        }

def search(word, seen, curind):
    possmoves = moves[curind]
    for x in possmoves:
        if x in seen:
            continue
        letter = board[x]
        newword = word + letter 
        if newword in allowed and len(newword) > 2:
            found.add(newword)
        if newword in interim:
            newseen = seen.copy()
            newseen.add(x)
            search(newword, newseen, x) 

for x in range(16):
    letter = board[x]
    search(letter,set([x]),x)

lens = defaultdict(int)
for x in found:
    lens[len(x)] += 1

for (k,v) in lens.iteritems():
    print k,":", v
print len(found)