在 Boggle.java 游戏中部署启发式算法以修剪搜索 space

Question

因此，我正在尝试编写一个 java 程序来模拟 Boggle 游戏。它输入两个文本文件，第一个是代表 nxn 板的文本文件，其中第一行包含板的尺寸，即 4x4.txt 文件的第一行将是数字 4，其余将是板本身.第二个 txt 文件将是一个包含所有可能的字典单词的文件。

我首先想验证我们用于从 nxn 网格生成所有可能的字符串输出的算法是否正确。我使用了深度优先搜索算法来做到这一点。

我相信这部分我是对的。但是，现在我要实施一种启发式方法来帮助识别死胡同并节省搜索浪费的单词和时间。我不知道这应该如何进行。任何帮助将不胜感激。

这是我到目前为止的代码。就像我说的，我的 depthFirstSearch 方法是正确的，并且给了我正确的输出。我也不喜欢使用 TreeSet 来存储字典单词，因为我什至不确定这是正确的。我这样做是因为我知道这是存储可能的字符串组合的正确 ADT。

import java.io.*;
import java.util.*;

public class Boggle {

    //Above main declare a static long int numWordsFormed=0;
    private static int numWordsFormed = 0;
    private static TreeSet<String> allPossWords = new TreeSet<String>();

    public static void main(String[] args) throws Exception
    {
        Scanner dfile = new Scanner(new FileReader(args[0]));
        TreeSet<String> dictionary = new TreeSet<String>();

        while(dfile.hasNext())
        {
            dictionary.add(dfile.next());
        }
        dfile.close();

        Scanner bfile = new Scanner(new FileReader(args[1]));
        int r = bfile.nextInt();
        int c = r;
        String[][] board = new String[r][c];

        for (int i = 0; i < r; i++) 
            for (int j = 0; j < c; j++)
                board[i][j] = bfile.next();

        for(int row = 0; row < board.length; row++)
            for(int col = 0; col < board[row].length; col++)            
                depthFirstSearch(board, row, col, "");

        for(String possWords : allPossWords)
            System.out.println(possWords);
    }

    public static void depthFirstSearch(String[][] board, int r, int c, String word)
    {
        word = word.concat(board[r][c]);
        ++numWordsFormed;
        allPossWords.add(word);

        if(((r-1) >= 0) && (Character.isLowerCase(board[r-1][c].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r-1, c, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r-1) >= 0) && ((c+1) < board[r-1].length) && (Character.isLowerCase(board[r-1][c+1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r-1, c+1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((c+1) < board[r].length) && (Character.isLowerCase(board[r][c+1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r, c+1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r+1) < board.length) && ((c+1) < board[r+1].length) && (Character.isLowerCase(board[r+1][c+1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r+1, c+1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r+1) < board.length) && (Character.isLowerCase(board[r+1][c].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r+1, c, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r+1) < board.length) && ((c-1) >= 0) && (Character.isLowerCase(board[r+1][c-1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r+1, c-1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((c-1) >= 0) && (Character.isLowerCase(board[r][c-1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r, c-1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r-1) >= 0) && ((c-1) >= 0) && (Character.isLowerCase(board[r-1][c-1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r-1, c-1, word);
            board[r][c] = board[r][c].toLowerCase();
        }
    }

}

Answer 1

首先，实现一个Trie，并在初始化时写入字典。任何单词的查找时间都是确定性的，因为单词的长度是从 Trie 的空根到叶子的最后一个字母的遍历时间。

然后，根据 Trie 的结构，创建启发式。

在 Boggle.java 游戏中部署启发式算法以修剪搜索 space

Deploying a Heuristic to Prune search space in a Boggle.java Game

java

heuristics

boggle