Solving Boggle-type word games in Python
Recently I’ve been spending a lot of my spare time learning the Python computer programming language. This all began because of an interest in the Google App Engine, which uses Python as the primary language. I decided that it’d been a while since I picked up a new programming language (the last being C#) and I knew I’d have some spare time over the holidays.
Anyhow, there are a number of excellent learning resources for Python, but I seem to learn best by doing. So, after tackling a number of levels in the Python challenge I decided to make my own challenge; Rack up a high score in Scramble and Scramble2, which is a “Boggle”-type game for Facebook and the iTouch/iPhone respectively.
photo credit: therichbrooks
The game is played on a 4×4 or 5×5 grid of letters. The object is to attain a high score. You score by connecting adjacent letters into a word. Longer words result in disproportionally higher scores. The minimum word length is 3. You cannot use a letter-space more than once in the same word.
I created a Python program which compared all possible paths to a dictionary of known words and then printed them out in order from longest to shortest. The program is admittedly lacking in a user-interface. You have to re-run it to change the board size and it’s not super-optimized for either speed or memory. However, it does work quite well and is fast enough to use. It takes about 20-30 seconds to do the initial load of all the paths and then takes between 1-5 seconds to compute possible words once you type in the values from the game.
Below are the results from my Python program (left) and showing my “high score” of 369 (right).
With a better dictionary you could improve the score. In the example above, my dictionary has 3 of the 5 seven-letter words but misses the eight-letter word in the puzzle.
You can download the Scramble Solver.py – Python source code. I used a list of words separated by carriage returns from a spell-checking “dictionary”. You are on your own for finding a word list. I’m providing the source code so that you can see it, not so you can beat the game :)
Below is a complete listing of the source code:
class wordlist:
"""
Create a clean list of words from the base dictionary
"""
def __init__(self, max_length):
# Constants
self._rawpath = 'en_us.dic'
self._maxlength = max_length
def load(self):
"""
Returns a clean list of words
"""
print 'Creating list of words...'
raw_dictionary = open(self._rawpath, 'r')
goodwords = set()
for line in raw_dictionary:
# Make sure we have a word of the correct size and not starting with a number and with no apostrophes
if (2 < len(line) < self._maxlength + 1
and line[0] not in ['0','1','2','3','4','5','6','7','8','9']
and "'" not in line):
# Strip off trailing \n and convert to lowercase
goodwords.add(line[:-1].lower())
raw_dictionary.close()
print 'Created list of words.'
return goodwords
class pathlist:
"""
Creates a path list which contains all possible paths through the grid.
"""
def __init__(self, board_size, max_length):
# Constants
self._boardsize = board_size
self._maxlength = max_length
# Properties
self.paths = []
def _traversepath(self, startindex, previouspath):
"""
Finds all the paths for a given starting point,
used recursively to explore adjacent segments
"""
# Immediately exit if we are trying to create a circular path
# or if the path length gets too long
if startindex in previouspath or len(previouspath) >= self._maxlength:
return
# Copy the path and then add the next segment
nextpath = previouspath[:]
nextpath.append(startindex)
# Only store paths of at least three letters
if len(nextpath) > 2:
self.paths.append(nextpath)
# Grab the row and column for the given startindex
row = startindex // self._boardsize
col = startindex % self._boardsize
# Traverse adjacent paths
# Up to 8 adjacent paths possible
# Row above: row - 1
if row - 1 >= 0 and col - 1 >= 0: self._traversepath(startindex - self._boardsize - 1, nextpath)
if row - 1 >= 0: self._traversepath(startindex - self._boardsize, nextpath)
if row - 1 >= 0 and col + 1 <= 3: self._traversepath(startindex - self._boardsize + 1, nextpath)
# Same row: row - 0
if col - 1 >= 0: self._traversepath(startindex - 1, nextpath)
if col + 1 <= 3: self._traversepath(startindex + 1, nextpath)
# Row below: row + 1
if row + 1 <= 3 and col - 1 >= 0: self._traversepath(startindex + self._boardsize - 1, nextpath)
if row + 1 <= 3: self._traversepath(startindex + self._boardsize, nextpath)
if row + 1 <= 3 and col + 1 <= 3: self._traversepath(startindex + self._boardsize + 1, nextpath)
def load(self):
"""
Returns a list of possible paths
"""
self.paths = []
print 'Creating the path list...'
# Generate self.paths by going through all positions
for i in range(0, self._boardsize ** 2):
self._traversepath(i, [])
print 'Created the path list.'
return self.paths
class solver:
"""
Class for solving 4x4 and 5x5 grid word puzzles using a dictionary
"""
def __init__(self, paths = None, dict = None):
"""
Loads up the dictionary and paths from file
"""
print 'Loading words...'
self.dictionary = dict
print 'Loaded %d words.' % len(self.dictionary)
print 'Loading paths...'
self.paths = paths
print 'Loaded %d paths.' % len(self.paths)
# initialize grid
self.grid = []
def _translate_path_to_letters(self, path, letters):
"""
Translates a numerical path to letters given a grid.
Returns a string
"""
output = ''
for p in path:
output += letters[p]
return output
def _get_intersecting_words(self):
"""
Finds the intersection between the dictionary words
and the (path-based) possible words
Returns a subset of the possible words
"""
realwords = {}
for word in self.dictionary:
if self.possiblewords.has_key(word):
realwords[word] = self.possiblewords[word]
return realwords
def get_words(self, letters):
"""
Returns a dictionary with keys of valid words.
The values of the dictionary are the paths taken to get those valid words.
For example, in the sample data set (4x4 board):
Key: genius
Value: [4, 8, 5, 6, 9, 10]
"""
output = ''
self.grid = letters
self.possiblewords = dict()
# Translate all paths into letters
print 'Translating all possible paths into possible words...'
for path in self.paths:
self.possiblewords[self._translate_path_to_letters(path, letters)] = path
print 'Translated paths into %d unique words.' % len(self.possiblewords)
print 'Finding possible real words...'
realwords = self._get_intersecting_words()
print 'Found %d possible real words.' % len(realwords)
return realwords
MAXLENGTH = 10
BOARDSIZE = 4
pl = pathlist(BOARDSIZE, MAXLENGTH)
wl = wordlist(MAXLENGTH)
s = solver(pl.load(), wl.load())
while True:
print 'Enter all %d lines in a row, with no spaces between them. Or, press ENTER to use the default values. Type "q" by itself to quit.' % BOARDSIZE
line = raw_input("line:").lower()
if line == 'q':
break
# Check to see if we should use the default values
if len(line) == 0:
print 'Using default values.'
# Assumes BOARDSIZE of 4 or 5 only
if BOARDSIZE == 4:
line = 'oiei' + 'gnic' + 'eusn' + 'oliy'
else:
line = ''
# Find all the possible words and their paths
wordset = [word for word in s.get_words(line).keys()]
# Print out the words, sorted from longest to shortest, ignoring the paths
for word in sorted(wordset, None, len, True):
print word
