Почему не работает Boggle Solver?

Question

Я пишу ошеломительный решатель, и я не знаю, где я ошибся в коде. Вот что у меня так далеко:

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) невероятно медленный, так как каждый раз сканирует весь список. В среднем это займет 40 000 итераций для словаря из 80 000 слов.

Более подходящей структурой данных будет набор деревьев или дерево префиксов (или trie). Оба оптимизированы для быстрого поиска и хорошо подходят для вышеупомянутой проверки префикса. Для набора деревьев будет удобен метод floor (). Посмотрите этот вопрос для получения информации о попытках в Java.

Answer 2

Этот ArrayList будет ОГРОМНЫМ! Вы должны попытаться использовать лучшую структуру данных, например, ArrayList<ArrayList<ArrayList<String>>> где первый индекс - первая буква слова, а второй индекс - вторая буква слова.

wordsPossible = new ArrayList<ArrayList<ArrayList<String>>>(26);
for (char c = 'a'; c <= 'z'; c++) {
    ArrayList<ArrayList<String>> temp = new ArrayList<ArrayList<String>>(26);
    wordsPossible.add(temp);
    for(char d = 'a'; d <= 'z'; d++) { 
        ArrayList<String> innerTemp = new ArrayList<String>();
        temp.add(innerTemp);
    }
}

// Snip

while(scanner.hasNext()){
  String str = scanner.nextLine();
  addWord(str);
}

// Snip

public void addWord(String str) {
  int first = str.toLowerCase().charAt(0) - 'a';
  int second = str.toLowerCase().charAt(1) - 'a';
  wordsPossible.get(first).get(second).add(str);
}

Тогда ищите подходящие слова, сначала добираясь до правильного внутреннего ArrayList без необходимости делать большой поиск.