Recursion
This is a recursive problem: when looking for the word NOON, we first scan the board looking for N and, when we find one, start there looking for the word OON, and, once we find an O, start there, scanning for the word ON, and so on.
We keep track of the letters we’ve seen, so we don’t re-use them in a path.
Note that we do this by creating a new list for step (seen = seen + ...)
so when we backtrack to a previous call frame, we’re back to the original
list of seen letters.
Things start with seen, which tries every space on the board for the start letter:
def find(board, word):
"""Can word be found in board?"""
# START SOLUTION
# print "%-6s%s,%s %-3s%-8s%-30s" % ("out", "y", "x", "bd", "word", "seen")
# Find starting letter --- try every spot on board and,
# win fast, should we find the word at that place.
for y in range(0, 5):
for x in range(0, 5):
if find_from(board, word, y, x, seen=set()):
return True
# We've tried every path from every starting square w/o luck.
# Sad panda.
return False
This calls find_from, which looks for the word starting at a particular spot, and recursively looks for the smaller (minus first letter) word in each NSWE direction.
def find_from(board, word, y, x, seen):
"""Can we find a word on board, starting at x, y?"""
# This is called recursively to find smaller and smaller words
# until all tries are exhausted or until success.
# Base case: this isn't the letter we're looking for.
if board[y][x] != word[0]:
# print "%-6s%d,%d %-3s%-8s%-30s" % ("NO", y, x, board[y][x], word, seen)
return False
# Base case: we've used this letter before in this current path
if (y, x) in seen:
# print "%-6s%d,%d %-3s%-8s%-30s" % ("SEEN", y, x, board[y][x], word, seen)
return False
# Base case: we are down to the last letter --- so we win!
if len(word) == 1:
# print "%-6s%d,%d %-3s%-8s%-30s" % ("WIN", y, x, board[y][x], word, seen)
return True
# Otherwise, this letter is good, so note that we've seen it,
# and try of all of its neighbors for the first letter of the
# rest of the word
# print "%-6s%d,%d %-3s%-8s%-30s" % ("OK", y, x, board[y][x], word, seen)
# This next line is a bit tricky: we want to note that we've seen the
# letter at this location. However, we only want the child calls of this
# to get that, and if we used `seen.add(...)` to add it to our set,
# *all* calls would get that, since the set is passed around. That would
# mean that once we try a letter in one call, it could never be tried again,
# even in a totally different path. Therefore, we want to create a *new*
# seen set that is equal to this set plus the new letter. Being a new
# object, rather than a mutated shared object, calls that don't descend
# from us won't have this `y,x` point in their seen.
#
# To do this, we use the | (set-union) operator, read this line as
# "rebind seen to the union of the current seen and the set of point(y,x))."
#
# (this could be written with an augmented operator as "seen |= {(y, x)}",
# in the same way "x = x + 2" can be written as "x += 2", but that would seem
# harder to understand).
seen = seen | {(y, x)}
if y > 0:
if find_from(board, word[1:], y - 1, x, seen):
return True
if y < 4:
if find_from(board, word[1:], y + 1, x, seen):
return True
if x > 0:
if find_from(board, word[1:], y, x - 1, seen):
return True
if x < 4:
if find_from(board, word[1:], y, x + 1, seen):
return True
# Couldn't find the next letter, so this path is dead
return False
There are print statements commented out; if you uncomment these, you can watch the logic being performed.