#!/usr/bin/env python
print "Welcome to Scramble with Cheaters!\n"
print "Please input the grid one one line using spaces to separate each row."
print "For example: scte hral lanb yema"
print "Also, please only type 'q' to reprseent 'qu'"
grid = raw_input().split()
print grid
# Get the number of rows and columns in the grid.
nrows, ncols = len(grid), len(grid[0])
# Get all words in the dictionary.
words = set(word.lower() for word in open('dictionary.txt').read().splitlines())
# Get all base words that build up to each word. This is also known as a trie.
# Ex., for the word "potato", add "p", "po", "pot", "pota", "potat" and "potato"
trie = set(word[:i] for word in words for i in range(2, len(word)+1))
# Get generator for neighboring letters.
def neighbors((x, y)):
for nx in range(max(0, x-1), min(ncols, x+2)):
for ny in range(max(0, y-1), min(nrows, y+2)):
yield nx, ny
# Recursive function to extend each base.
def expand(prefix, path):
if prefix in words: # If this base is a word,
yield (prefix, path) # add it to the generator as a match.
for x, y in neighbors(path[-1]): # Otherwise, try all the neighbors.
if (x, y) not in path: # If the neighbor isn't already in the path,
letter = grid[y][x] # Get the letter from the grid.
if letter == 'q': letter = 'qu' # Replace 'q' with 'qu'
expanded_prefix = prefix + letter # Add the letter to the base.
# If the base makes sense to add from the dictionary,
if expanded_prefix in trie:
# Recursively check extending each base to its neighbors,
# making sure to update the path.
for result in expand(expanded_prefix, path + ((x, y),)):
yield result
# Solve the Scramble with Friends grid.
def solve():
# For every row in the grid,
for y, row in enumerate(grid):
# For every column in each row,
for x, prefix in enumerate(row):
# For every result that comes from each starting point,
for result in expand(prefix, ((x, y),)):
# Add the result to the generator.
yield result
# Print all words.
print '\n'.join(sorted(set(word for (word, path) in solve()), key=len))
Cartoon Clouds
Mountains
Sunrise
Clouds
Green Clouds
None
I used a prefix tree (tier) built on a dictionary file that was made available by Zynga, and used Depth-First Search to expand to each neighbor after checking the string built so far against the prefix tree. Works pretty fast. 
Help
Register Now!