如何遞歸檢查一個在boggle類型遊戲中的答案

Question

作爲一個練習，我一直試圖在python中構建一個非GUI boggle類型的遊戲。到目前爲止，用戶可以輸入棋盤大小（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塊。如果這個詞不是太長或者沒有太多可能性，它就會有效。例如，試圖找到「原糖」在下面，將無法正常工作，即使它是存在的：

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