# Boggle in Python

This is a solver for the game “Boggle”. The aim of the game is to find as many words as possible in a 4-by-4 grid randomly filled with letters. You are allowed to go up, down, left, right, or diagonally, but not use the same letter more than once.

First, here’s a prefix tree, which is the ideal structure for looking up words one letter at a time:

class PrefixTree(object):
def __init__(self, letter=None):
self.letter = letter
self.children = {}
self.stop = False

if len(word):
letter = word
word = word[1:]
if letter not in self.children:
self.children[letter] = PrefixTree(letter);
else:
self.stop = True
return self

def find_letter(self, letter):
if letter not in self.children:
return None
return self.children[letter]

def __repr__(self):
return "PrefixTree(letter={0}, stop={1})".format(self.letter, self.stop)


Here’s the code for the game solver itself. It simply searches recursively starting at each cell in the game, and looks up the sequences of letters it builds up in the prefix tree:

from random import choice
from prefixtree import PrefixTree

class Boggle(object):
def __init__(self, board=None):
self.size = 4
if board is None:
self.board = []
for i in range(0, self.size):
self.board.append([])
for j in range(0, self.size):
self.board[i].append(Boggle.random_letter())
else:
self.board = board

@staticmethod
def random_letter():
return chr(choice(range(65,91)))

def play(self, tree, found):
for r in range(0, self.size):
for c in range(0, self.size):
self.search_r(tree, found, r, c)

def search_r(self, tree, found, row, col, path=None, node=None, word=None):
letter = self.board[row][col]
if node is None or path is None or word is None:
node = tree.find_letter(letter)
path = [(row, col)]
word = letter
else:
node = node.find_letter(letter)
path.append((row, col))
word = word + letter
if node is None:
return
elif node.stop:
for r in range(row - 1, row + 2):
for c in range(col - 1, col + 2):
if (r >= 0 and r < self.size
and c >= 0 and c < self.size
and not (r == row and c == col)
and (r, c) not in path):
self.search_r(tree, found, r, c, path[:], node, word[:])

def __repr__(self):
return "Boggle(size={0}, board={1})".format(self.size, self.board)


I used this dictionary as a source of words. You may want to use a slightly smaller one.
Here is the main program:

def load_tree(tree):
with open('dictionary.txt') as f:
for line in f:
word = line.rstrip().upper()

def main():
boggle = Boggle()
tree = PrefixTree()