A Boggle Board Solver in Python

:Author: Dean Hall
:Date: 2005/08/30

Classes to brute-force search for all words on a Boggle board.  BoglDict is
used to create and use a Dictionary containing official Scrabble (tm) words.
BoglPlayer accepts table input, performs the search algorithm and prints the

Generates a 27-ary tree for word lookup.
Looks up whole word or first-N letters.
Imports/exports tree struct.

Scrabble Dictionary comes from::


Command line Usage::

    > python bogl.py

Interactive Usage::

    >>> import bogl
    >>> p = bogl.BoglPlayer()
    >>> p.get_table()
    >>> p.find_words()
    >>> p.print_words()

Building the dictionary (2-letter words filtered out)::

    >>> bd = bogl.BoglDict('113809of.fic')
    File (113809of.fic) is a word list.
    >>> bd.numwords
    >>> bd.append_from_word_list(open('4160offi.cia','r'))
    >>> bd.numwords
    >>> bd.export_dict(open("bogldict.pkl",'wb'))

import cPickle

class BoglDict(object):
    """A 27-ary tree for per-character word lookup."""

    # Data filenames
    boglDictFn = "bogldict.pkl"
    wordList1Fn = "113809of.fic"
    wordList2Fn = "4160offi.cia"

    def __init__(self, fn = boglDictFn):
        """Create an initial tree using data from fn.
        fn must contain a word list or a pickled tree.

        self.tree = {}
        self.longest = 0
        self.numwords = 0

        # Try to open the file as a pickle; if not, then import as a wordlist
        f = open(fn, 'r')
            self.tree, self.longest, self.numwords = cPickle.load(f)
            print "File (%s) is a pickle file." % fn
        except Exception, e:
            print "File (%s) is a word list." % fn

    def append_from_word_list(self, f):
        """Appends entries to the tree using the words in the given file"""

        longest = self.longest
        numwords = self.numwords

        # Add each letter of each >2 length word in the file to the tree
        for word in f.read().splitlines():
            if len(word) < 3:
            d = self.tree
            for letr in word:
                if not d.has_key(letr):
                    d[letr] = {}
                d = d[letr]

            # Adding the whole word as one entry signals the end-of-word
            d[word] = True

            # Count the number of words added
            numwords += 1

            # Track the length of the longest word
            l = len(word)
            if l > longest:
                longest = l

        self.numwords = numwords
        self.longest = longest

    def is_start_of_word(self, word):
        """Returns true if partial word is in the tree"""
        d = self.tree
        for letr in word:
            if not d.has_key(letr):
                return False
            d = d[letr]
        return True

    def is_word(self, word):
        """Returns true if word is in the tree with an end-of-word marker"""
        d = self.tree
        for letr in word:
            if not d.has_key(letr):
                return False
            d = d[letr]
        return d.has_key(word) and d[word] == True

    def export_dict(self, f):
        """Writes the tree as a pickle to the given file object"""
        cPickle.dump((self.tree, self.longest, self.numwords), f, True)

class BoglPlayer(object):
    """Methods to create list of valid words from entry"""

    def __init__(self, bogldict=None):
        """Load the dictionary (create it if needed)"""
        self.table = []
        self.wordlist = []
        self.bogldict = bogldict or BoglDict()

    def get_table(self,):
        """Ask for and store the letters"""
        print "Enter letters one row at a time, no spaces."
        t = []
        i = 1
        tabledim = 10
        while i <= tabledim:
            row = raw_input("Enter row %d > " % i)
            if i == 1: tabledim = len(row)
            else: assert len(row) == tabledim
            i += 1
        self.table = t

    def print_words(self,):
        """Find and print the words"""
        if not self.wordlist:
        print self.wordlist

    def find_words(self,):
        """Find words in the table that are also in the dict"""
        tabledim = len(self.table)
        self.wordlist = []

        if not self.table:

        # Iterate over each letter in each row
        check_words = self.check_words
        for i in range(tabledim):
            for j in range(tabledim):
                check_words(i, j, "", [])
        print "Found %d words." % len(self.wordlist)

    def check_words(self, i, j, partword, usedcoords):
        """Add the current word to the wordlist if it is in the dictionary and
        recursively check the word formed by appending the neighboring letter
        in all 8 directions being sure not to reuse any coordinate.

        # Append the current letter to the test word
        letr = self.table[i][j]
        if letr == 'q':
            testword = partword + "qu"
            testword = partword + letr

        # Add word if it is in the dict and not already in the word list
        if self.bogldict.is_word(testword) and testword not in self.wordlist:

        # If the test word is a valid prefix
        if self.bogldict.is_start_of_word(testword):

            # Push the current coordinate
            usedcoords.append((i, j))

            tabledim = len(self.table)

            # Check each letter starting at high-noon going clockwise
            # Be sure to not re-use a coordinate and that the coord is in-bounds
            check_words = self.check_words
            if (i  , j-1) not in usedcoords and j-1 >= 0:
                check_words(i  , j-1, testword, usedcoords)
            if (i+1, j-1) not in usedcoords and i+1 < tabledim and j-1 >= 0:
                check_words(i+1, j-1, testword, usedcoords)
            if (i+1, j  ) not in usedcoords and i+1 < tabledim:
                check_words(i+1, j  , testword, usedcoords)
            if (i+1, j+1) not in usedcoords and i+1 < tabledim and j+1 < tabledim:
                check_words(i+1, j+1, testword, usedcoords)
            if (i  , j+1) not in usedcoords and j+1 < tabledim:
                check_words(i  , j+1, testword, usedcoords)
            if (i-1, j+1) not in usedcoords and i-1 >= 0 and j+1 < tabledim:
                check_words(i-1, j+1, testword, usedcoords)
            if (i-1, j  ) not in usedcoords and i-1 >= 0:
                check_words(i-1, j  , testword, usedcoords)
            if (i-1, j-1) not in usedcoords and i-1 >= 0 and j-1 >= 0:
                check_words(i-1, j-1, testword, usedcoords)

            # Pop the current coord

def main():
    bogldict = BoglDict()
        p = BoglPlayer(bogldict)

if __name__ == "__main__":