如何在Boggle遊戲板中對單詞進行遞歸搜索？

Question

有人可以用psuedocode或甚至遞歸公式來幫助我，該遞歸公式描述了Boggle板中單詞的遞歸搜索，因此我可以開始嗎？

Answer 1

要存儲有效的單詞，需要檢查的方法的數據結構是給定某個有效單詞的字符串前綴，並給出字符串需要有效的單詞，例如，數據結構爲Trie。

要找到所有可能的有效單詞，我們必須爲每個位置開始單詞，並遞歸訪問每個未訪問過的鄰居。下面是實現搜索的所有有效的話對給定表Python類的方法有兩種：

def solve_with(self, ind, inds_passed, word): 
    word += self.table[ind[0]][ind[1]] # Add next character 
    if self.trie.is_prefix(word):  # Is current string prefix of valid word 
     if len(word) > 2 and self.trie.is_word(word): # Is current string whole word 
      self.ret.add(word) 
     inds_passed.add(ind)   # Set this position as visited 
     for n in self.neigbours(ind): # Pass through all neighbours 
      if n not in inds_passed: # If not visited already 
       self.solve_with(n, inds_passed, word) # Recursive call 
     inds_passed.discard(ind)  # Remove position as visited 

def solve(self): 
    self.ret = set()     # Set of all word found on table 
    for x in xrange(0, self.dim):  # Start search with each position 
     for y in xrange(0, self.dim): 
      self.solve_with((x,y), set(), '') 
    return self.ret 

Answer 2

假設你有一個單詞列表的地方，可能存儲在特里數據結構（我創建了一個工作與特里對提高其效率的意見here）。

一旦你有一個Trie結構（一個前綴樹），它允許你根據它們的前綴搜索單詞，你會想要使用類似下面的psudo-code的遞歸方法。

char[][] gameBoard = new char[4][4]; 
List<String> wordList = new ArrayList<String>(); 
//fill in the game board with characters 
//Start the word search at each letter 
for(int x = 0; x < 4; x++){ 
    for(int y = 0; y < 4; y++){ 
     recursiveWordSearch(x, y, ""); 
    } 
} 
recursiveWordSearch(int x, int y, String word){ 
    //Concatenate gameBoard[x][y] to word. 
    //Check to see if word is a valid word (check against your word list). 
    //If word, add to wordList 

    /*Check word list to see if any words contain current prefix. If not, 
    then there's no point in continuing further (return). IE if AQZ isn't the 
    start of any word at all in the list, no reason to keep adding letters, it's 
    never going to make a word. */ 

    //Otherwise recursively call this method moving left/right/up/down 
    recursiveWordSearch(x+1, y, word); //move right 
    recursiveWordSearch(x, y+1, word); //move up 
    recursiveWordSearch(x-1, y, word); //move left 
    recursiveWordSearch(x, y-1, word); //move down 
    /*You'll want to make sure that x-1, x+1, y-1 and y+1 are valid values before 
    sending them. */ 


}