java - Boggle ゲーム ボードで単語を再帰的に検索するにはどうすればよいですか?

Question

疑似コードや、Boggle ボードで単語を再帰的に検索する方法を説明する再帰的な式を教えてもらえますか?

Answer 1

おそらくトライデータ構造に格納されている可能性が高いどこかで利用可能な単語リストがあると仮定します（効率を改善するためのコメント付きの実用的なトライを作成しましたhere）。

プレフィックスに基づいて単語を検索できるトライ構造 (プレフィックス ツリー) ができたら、次の疑似コードのような再帰的な方法を使用する必要があります。

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. */


}

Answer 2

有効な単語を格納するには、 Trieデータ構造など、有効な単語の文字列プレフィックスが指定され、有効な単語が指定された文字列をチェックするメソッドを含むデータ構造が必要です。

可能なすべての有効な単語を見つけるには、各位置の単語を開始し、訪問されていない隣接する各単語を再帰的に訪問する必要があります。指定されたテーブルですべての有効な単語の検索を実装する python クラスの 2 つのメソッドを次に示します。

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