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 def add(self, word): if len(word): letter = word[0] word = word[1:] if letter not in self.children: self.children[letter] = PrefixTree(letter); return self.children[letter].add(word) 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: found.add(word) 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() tree.add(word) def main(): boggle = Boggle() tree = PrefixTree() load_tree(tree) found = set() boggle.play(tree, found) for word in sorted(found): print word print boggle if __name__ == '__main__': main()