How to recursively check an answer in a boggle type game

As an exercise, I have been trying to build a non-GUI boggle type game in python. So far, the user is able to enter a board size (4x4,5x5,etc). The 'array' of letters appears and then the user may type in a word that they think is a valid option.

I wanted to check if the entered word was valid by using a recursive function. On small boards my solution seems to work fine. On larger boards however, words with similar starts and multiple paths don't register. I have a feeling that it is because the last part of my function is not able to step back far enough if the current path ends without finding a correct word.

Here is what I have so far:

def isAdjacent(word, wordLetter, possibleStarts, arrayDict, currWord, start):

  #'word' is the word entered. 'wordLetter' is the current letter being looked for.
  #'possibleStarts' is a list of tuples of the possible starting locations and subsequent positions of each found letter.
  #'arrayDict' is a dictionary associating each position ((0,1), etc) with a game letter.
  #'currWord' is used to check whether or not a word has been found.
  #'start' is the tuple in possibleStarts that should be used.

  if currWord == word:
    return 1
  x = possibleStarts[start][0]
  y = possibleStarts[start][1]
  arrayDict[x,y] = 0
  optionsList = [(x - 1, y - 1), (x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y), (x + 1, y + 1)]
  newStarts = []
  count = 0
  count2 = 0
  for option in optionsList: 
    count += 1
    if option in arrayDict:
      if arrayDict[option] == word[wordLetter]:
        if count2 < 1:
          currWord += word[wordLetter]
          arrayDict[option] = 0
          count2 += 1
        newStarts.append(option) 
    if count == 8 and newStarts:                                                        
      return isAdjacent(word, wordLetter + 1, newStarts, arrayDict, currWord, start)    
  try:
    if currWord != word:
      if wordLetter > 2:
        return isAdjacent(word, wordLetter - 1, possibleStarts, arrayDict, currWord[:-1], start - 1) 
      else:
        return isAdjacent(word, wordLetter, possibleStarts, arrayDict, currWord, start - 1) 
  except:
    pass

I believe that at least part of the problem lies in the try block at the end of the fun开发者_C百科ction. It works if the word is not too long or if there are not too many possibilites. For example, attempting to find 'raws' in the following, will not work, even though it is there:

W T S V
A X A H
S R T S
A B A W

I am certain that this can be done with a rather simple recursive function, but after many hours, I am lost. Oh, I would rather not generate all of the possible words beforehand. The goal of this was to use recursion to find an entered word.

Any help is greatly appreciated!

---

Interesting exercise, I had a crack at it. I post the code below so consider this a spoiler alert. For general tips:

• Break the code down into smaller chunks - one function to rule them all doesn't take you far.
• When doing recursion, start by finding the base cases, ie. when will the function not recurse.
• Let each subfunction know only what it needs to know.

That's about it. I'm a bit rusty on the complete rules of Boggle and I'm not completely sure what you are doing the entire time, but this what I've come up:

---

def paths(grid, x, y, l):
    """Returns a list of positions that the required letter is at"""

    positions = [(x - 1, y - 1), (x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y), (x + 1, y + 1)]
    return [p for p in positions if p in grid and grid[p] == l]

def matchWord(grid, pos, word):
    """Returns true if the word was found in the grid starting from pos"""
    if word == "" : return True
    pos_paths = paths(grid, pos[0], pos[1], word[0])
    if pos_paths == [] : return False

    return any(matchWord(grid, the_pos, word[1:]) for the_pos in pos_paths)

def wordInGrid(grid, word):
    """returns true if the word is in the grid"""
    return any(matchWord(grid, key, word[1:]) for (key, val) in dict.iteritems(grid) if val == word[0])


gr_dict = {(0, 1): 'T', (1, 2): 'A', (3, 2): 'A', (0, 0): 'W', (3, 3): 'W', (3, 0): 'A', (3, 1): 'B', (2, 1): 'R', (0, 2): 'S', (2, 0): 'S', (1, 3): 'H', (2, 3): 'S', (2, 2): 'T', (1, 0): 'A', (0, 3): 'V', (1, 1): 'X'}

print wordInGrid(gr_dict, "RATS")
print wordInGrid(gr_dict, "WASABATAS")