java - 如何在 Boggle 游戏板上递归搜索单词？

Question

有人可以帮助我使用伪代码甚至是描述在 Boggle 板上递归搜索单词的递归公式，这样我就可以开始了吗？

Answer 1

假设您在某处有一个可用的单词列表，可能存储在 Trie 数据结构中（我创建了一个有效的 Trie，并在此处添加了关于提高其效率的评论）。

一旦你有了一个允许你根据前缀搜索单词的 Trie 结构（前缀树），你会想要使用类似于以下伪代码的递归方法。

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;
}