java - 为什么 Boggle Solver 不起作用？

Question

我正在编写一个 boggle 求解器，但我不知道我的编码哪里出错了。这是我目前所拥有的:

public class Boggle {
char[][] letters;
ArrayList <String> wordsPossible;
boolean[][] lettersUsed;
ArrayList<String> wordsMade = new ArrayList<String>();


public static void main(String[] args) {
    Boggle boggle = new Boggle();

    boggle.findWords();
}

public Boggle(){
    letters = new char[4][4];
    letters[0][0] = 'a';
    letters[0][1] = 'd';
    letters[0][2] = 'e';
    letters[0][3] = 'h';
    letters[1][0] = 's';
    letters[1][1] = 't';
    letters[1][2] = 'i';
    letters[1][3] = 'p';
    letters[2][0] = 's';
    letters[2][1] = 'k';
    letters[2][2] = 'c';
    letters[2][3] = 'e';
    letters[3][0] = 'u';
    letters[3][1] = 'f';
    letters[3][2] = 'r';
    letters[3][3] = 'o';

    Scanner scanner = null;
    try {
        scanner = new Scanner(new File("brit-a-z.txt"));
    } catch (FileNotFoundException ex) {
        Logger.getLogger(Boggle.class.getName()).log(Level.SEVERE, null, ex);
    }
    wordsPossible = new ArrayList<String>();
    while(scanner.hasNext()){
        String str = scanner.nextLine();
        wordsPossible.add(str);
    }
    lettersUsed = new boolean[4][4];
}

public void findWords(){
    for(int i=0; i<letters.length; i++){
        for(int j=0; j<letters[i].length; j++){
            //findWords(jLabels[i][j].getText(), i, j, labelsUsed);
            findWords(Character.toString(letters[i][j]), i, j, lettersUsed);
            System.out.println("Done");
        }
    }
    for(int i=0; i<wordsMade.size(); i++){
        System.out.println(wordsMade.get(i));
    }
}

public void findWords(String word, int iLoc, int jLoc, boolean[][] lettersUsed){
    if(iLoc < 0 || iLoc >= 4 || jLoc < 0 || jLoc >= 4){
        return;
    }

    if(lettersUsed[iLoc][jLoc] == true){
        return;
    }

    word += letters[iLoc][jLoc];
    lettersUsed[iLoc][jLoc] = true;

    if(word.length() >= 3 && wordsPossible.contains(word)){
        System.out.println(word);
        wordsMade.add(word);
    }

    findWords(word, iLoc-1, jLoc, lettersUsed);
    findWords(word, iLoc+1, jLoc, lettersUsed);
    findWords(word, iLoc, jLoc-1, lettersUsed);
    findWords(word, iLoc, jLoc+1, lettersUsed);
    findWords(word, iLoc-1, jLoc+1, lettersUsed);
    findWords(word, iLoc-1, jLoc-1, lettersUsed);
    findWords(word, iLoc+1, jLoc-1, lettersUsed);
    findWords(word, iLoc+1, jLoc+1, lettersUsed);

    lettersUsed[iLoc][jLoc] = false;
}

它只是运行，很少会说找到了一个词。它也需要很长时间才能运行，大约一个小时。我看不出我的错误在哪里，我也看不出我可以在哪里犯错。任何帮助都会很棒!

Answer 1

这将在所有 10-、11-、12-、13-、14- 等字母单词中进行组合爆炸式搜索。一旦当前 word 不是字典中任何单词的前缀，您应该添加代码来修剪搜索。

此外，您正在使用 ArrayList 作为单词列表。使用 wordsPossible.contains(word) 搜索平面列表非常慢，因为它每次都会扫描整个列表。对于一个包含 80,000 个单词的词典，这平均需要 40,000 次迭代。

更合适的数据结构是 tree set或 prefix tree (或尝试)。两者都针对快速查找进行了优化，非常适合上述前缀检查。对于树集，ceiling()方法会很方便。参见 this question有关 Java 中的尝试的信息。