Boggle Solver in Python

board.txt

2 2
R Y
A N

board_2.txt

4 4
S N X P
P A X L
A E E Qu
N I S H

board_3.txt

3 3
R Y A
N W A
S T O

boggle.py

"""
Solves a "Boggle" game board by finding all solutions.

See http://www.python.org/doc/essays/graphs.html
"""
import operator
import sys
# from collections import Counter
from collections import defaultdict


def get_words(inputFile, norm=None):
  words = []
	with open(inputFile, "r") as f:
		for line in f:
			if norm:
				line = norm(line)
			words.append(line)

	return words

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if not graph.has_key(start):
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath: return newpath
	return None

def find_all_paths(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return [path]
	if not graph.has_key(start):
		return []
	paths = []
	for node in graph[start]:
		if node not in path:
			newpaths = find_all_paths(graph, node, end, path)
			for newpath in newpaths:
				paths.append(newpath)
	return paths

def path_to_word(board, path):
	return "".join(board[pos[0]][pos[1]] for pos in path)

def nodes_from_board(board):
	nodes = []
	for i in range(len(board)):
		for j in range(len(board[0])):
			nodes.append((i ,j))

	return nodes

def graph_from_board(board):
	neighborOffsets = (
		(-1, -1), (-1, 0), (-1, 1),
		(0, -1), (0, 0), (0, 1),
		(1, -1), (1, 0), (1, 1),
	)

	graph = {}
	nodes = nodes_from_board(board)
	for node in nodes:
		graph[node] = []

		for dn in neighborOffsets:
			if dn == (0, 0):
				continue
			neighbor = node[0] + dn[0], node[1] + dn[1]
			if (neighbor[0] >= 0 and neighbor[0] < len(board) and
				neighbor[1] >= 0 and neighbor[1] < len(board[0])):
				graph[node].append(neighbor)

	return graph

def normalize(s):
	return s.strip().lower()

def summarize_results(result):
	print "Found {} unique words and {} paths".format(len(result.keys()), sum(len(v) for v in result.values()))

	counts = {}
	for k, v in result.iteritems():
		counts[k] = len(v)

	for k, v in sorted(counts.iteritems(), key=operator.itemgetter(1)):
		print "{word: <15} {numSolutions}".format(word=k, numSolutions=v)

if __name__ == "__main__":
	words = get_words("/usr/share/dict/words", norm=normalize)
	words = dict((w, None) for w in words)

	board = []
	for l, line in enumerate(sys.stdin):
		line = line.strip()
		if not line: continue
		if l == 0:
			n, m = line.split()
			continue
		else:
			board.append(line.split())

	nodes = nodes_from_board(board)
	graph = graph_from_board(board)

	solutionDetails = defaultdict(list)
	numNodes = len(nodes)

	for i in range(numNodes):
		for j in range(numNodes):
			if i == j:
				continue
			start, end = nodes[i], nodes[j]
			print start, end

			for path in find_all_paths(graph, start, end):
				# candidateWord = normalize("".join(board[pos[0]][pos[1]] for pos in path))
				candidateWord = normalize(path_to_word(board, path))
				if candidateWord in words:
					solutionDetails[candidateWord].append(path)
					print "{:0>4} {: >15}: {}".format(len(solutionDetails.keys()), candidateWord, path)

	summarize_results(solutionDetails)

Makefile

profile:
  python -m cProfile foo.py < board_3.txt