如何在Boggle游戏板中递归搜索单词？

Question

有没有人可以帮我写一个伪代码，甚至是一个递归公式，用来描述在Boggle板上递归搜索单词的过程，这样我就可以开始了？

Answer 1

假设你在某个地方有一个可用的单词列表，可能存储在一个Trie数据结构中(我已经创建了一个工作Trie，其中包含关于提高其效率的注释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. */


}

Answer 2

为了存储有效词，具有检查方法的数据结构被赋予某个有效词的字符串前缀，并且被赋予字符串需要一个有效词，例如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 3

使用DFS方法的Java实现

import java.util.Arrays;

public class WordBoggle {

static int[] dirx = { -1, 0, 0, 1 };
static int[] diry = { 0, -1, 1, 0 };

public static void main(String[] args) {
    char[][] board = { { 'A', 'B', 'C', 'E' }, { 'S', 'F', 'C', 'S' }, { 'A', 'D', 'E', 'E' } };

    String word = "ABFSADEESCCEA";
    System.out.println(exist(board, word));
}

static boolean exist(char[][] board, String word) {
    if (board == null || board.length == 0 || word == null || word.isEmpty())
        return false;
    boolean[][] visited = new boolean[board.length][board[0].length];
    for (int i = 0; i < board.length; i++) {
        resetVisited(visited);
        for (int j = 0; j < board[0].length; j++) {
            if (board[i][j] == word.charAt(i)) {
                return DFS(board, word, i, j, 1, visited);
            }
        }
    }
    return false;
}

static void resetVisited(boolean[][] visited) {
    for (int l = 0; l < visited.length; l++) {
        Arrays.fill(visited[l], false);
    }
}

static boolean DFS(char[][] board, String word, int i, int j, int k, boolean[][] visited) {
    visited[i][j] = true;
    if (k >= word.length())
        return true;
    for (int z = 0; z < 4; z++) {
        if (isValid(board, i + dirx[z], j + diry[z], visited)) {
            if (word.charAt(k) == board[i + dirx[z]][j + diry[z]]) {

                return DFS(board, word, i + dirx[z], j + diry[z], k + 1, visited);
            }

        }
    }
    return false;
}