What follows is a fast solver for the Scramble Facebook game.
DICT = open('/users/jsomers/Documents/Work/Project Euler/TWL06.txt', 'r')
WORDS = [a.strip() for a in DICT.readlines()]
"Takes a string and builds a board, represented by a list of rows."
upper = string.upper()
raw = list(upper)
# handle a Q
i = raw.find('q')
raw[i] = 'qu'
assert len(raw) == 16, 'Board must be 4x4!'
rows = [raw[i:i + 4] for i in range(0, len(raw), 4)]
""" Takes a board and returns, for each letter, a list of its peers.
We check all possible surrounding squares, and 'pass' when one would
be out of list index range.
pgroups = 
for i, row in enumerate(board):
for j, col in enumerate(row):
# The i, j components in a node are for disambiguation, since
# some puzzles have more than one 'A', for instance.
peers = [(col, i, j)]
checks = [(1, 0), (1, 1), (1, -1), (-1, 0), (-1, 1), (-1, -1),
(0, -1), (0, 1)]
for c in checks:
pr_i, pr_j = i + c, j + c
if pr_i >= 0 and pr_j >= 0: # No wraparound
pr = board[pr_i][pr_j]
peers.append((pr, pr_i, pr_j))
def build_words(board, prefix, node, wordlist, nodepath, words):
""" This function does the heavy lifting. It takes a (prefix, node) combo
and tries to add letters to it by checking the node's peers. Recursion is
okay here since the search space shrinks quickly.
nodepath = nodepath[:len(prefix)] # Hack
peer_list = [p for p in pgroups(board) if p == node]
pared_peer_list = [n for n in peer_list if n not in nodepath]
pared_wordlist = [i for i in wordlist if i.startswith(prefix)]
for peer in pared_peer_list[1:]: # Exclude self
l = peer
new = prefix + l
if new in pared_wordlist:
if [i for i in pared_wordlist if i.startswith(new)]:
build_words(board, new, peer, pared_wordlist, nodepath, words)
def length(a, b):
return cmp(len(a), len(b))
the_board = board(string)
words = 
for pgroup in pgroups(the_board):
node = pgroup
words += build_words(the_board, node, node, WORDS, , )
solution = sorted([a for a in set(words) if len(a) > 2])