如何递归检查一个在boggle类型游戏中的答案

作为一个练习，我一直试图在python中构建一个非GUI boggle类型的游戏。到目前为止，用户可以输入棋盘大小（4x4,5x5等）。出现字母'数组'，然后用户可以键入他们认为是有效选项的单词。如何递归检查一个在boggle类型游戏中的答案

我想通过使用递归函数检查输入的单词是否有效。在小板上我的解决方案似乎工作正常。然而，在较大的棋盘上，具有类似起始和多个路径的单词不会注册。我有一种感觉，那是因为如果当前路径没有找到正确的单词，我的函数的最后一部分就不能够退回到足够远的地步。

这是我到目前为止有：

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块。如果这个词不是太长或者没有太多可能性，它就会有效。例如，试图找到“原糖”在下面，将无法正常工作，即使它是存在的：

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

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

任何帮助，非常感谢！

来源

2011-04-24 Gitarooman

不合格'except'应该*真的*命名一个特定的异常类型。很难调试那样的代码。 – 2011-04-24 20:27:16

作为一个练习，这应该很有趣，但要注意栈的大小相当大，但有限，所以你可以得到一个_stack overflow_（这在某种程度上适用于此）。 – extraneon 2011-04-24 20:27:55

是的，'尝试：...除了：通过'是撒旦的产卵（或上帝，取决于你更糟糕的是：p） – ThiefMaster 2011-04-24 20:28:25

有趣的运动，我有一个裂缝。我发布下面的代码，所以考虑这个扰流警报。对于一般提示：

将代码分解成更小的块 - 一个函数来统治它们并不会带你太远。
在进行递归时，首先找到基本案例，即。什么时候功能不是递归。
让每个子功能只知道它需要知道什么。

就是这样。我在惊奇的完整的规则有点生疏，我不能完全肯定自己在做什么的全部时间，但这个我想出什么：

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

来源

2011-04-24 21:44:41

如何递归检查一个在boggle类型游戏中的答案

回答

相关问题