如何在拼字游戏中递归地检查答案

Question

作为练习，我一直在尝试用python构建一个非gui的拼字游戏。到目前为止，用户可以输入电路板尺寸(4x4,5x5等)。出现字母"数组"，然后用户可以输入一个他们认为是有效选项的单词。

我想使用递归函数检查输入的单词是否有效。在小板我的解决方案似乎工作良好。然而，在较大的电路板上，具有相似开头和多条路径的单词不会注册。我有一种感觉，这是因为如果当前路径结束时没有找到正确的单词，我的函数的最后一部分无法退后足够远。

到目前为止我写的是:

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

我相信至少部分问题在于函数末尾的try块。如果单词不太长或者没有太多的可能性，它就会起作用。例如，尝试在下面查找'raws'将无法工作，即使它存在:

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

我确信这可以用一个相当简单的递归函数来完成，但是几个小时后，我迷路了。哦，我宁愿不事先生成所有可能的单词。这样做的目的是使用递归来查找输入的单词。

任何帮助都非常感谢!

Answer 1

有趣的练习，我试了一下。我把代码贴在下面，所以把它当作一个剧透警报。一般提示:

• 将代码分解成更小的块-一个函数来控制它们并不能让你走得更远。
• 在进行递归时，首先要找到基本情况，即。当函数不递归时
• 让每个子函数只知道它需要知道的。

就是这样。我对拼字游戏的完整规则有点生疏了，我不完全确定你一直在做什么，但这是我想到的:

---

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")