Why doesn't thins Boggle Solver work?

Question

I am writing a boggle solver and I don't know where I went wrong in my coding. Here is what I have so far:

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

}

It just runs and will rarely ever say that a word was found. It also takes a really long time to run, about an hour. I can't see where my mistake is, and I don't see where I could have made one. Any help would be great!

Just out of curiosity, how large is `brit-a-z.txt`. Does it contain every word in the English language? — Joel Christophel, Dec 03 '12 at 22:10

score 3 · Answer 1 · edited May 23 '17 at 10:30

3

This is going to have a combinatorial explosion searching through all 10-, 11-, 12-, 13-, 14-, etc. letter words. You should add code to prune the search once the current word is not a prefix of any word in the dictionary.

Also, you're using an ArrayList for the list of words. Searching through a flat list with wordsPossible.contains(word) is incredibly slow as it will scan the entire list each time. On average this will take 40,000 iterations for an 80,000 word dictionary.

A more suitable data structure would be a tree set or prefix tree (or trie). Both are optimized for fast lookup, and are well-suited for the above-mentioned prefix check. For a tree set, the ceiling() method would be handy. See this question for information about tries in Java.

edited May 23 '17 at 10:30

Community

1
1

answered Dec 03 '12 at 22:24

John Kugelman

349,597
67
533
578

Ok, i thought of that before but I didn't think it would help. After realizing how much useless words are being tested, I am going to implement this. Thanks! – user1872912 Dec 03 '12 at 22:26
Thanks for the suggestion and link. I am now testing words to see if they are prefixes to words in the dictionary. That method works great, however, it never says any of the potential words are actual words ever. Any suggestions for this? – user1872912 Dec 03 '12 at 22:40

score 0 · Answer 2 · answered Dec 03 '12 at 22:25

That ArrayList is going to be HUGE! You should try using a better data structure, for example, an ArrayList<ArrayList<ArrayList<String>>> where the first index is the first letter of the word, and the second index is the second letter of the word.

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

Then look up matching words by first getting to the correct inner ArrayList without having to do a big search.

This makes sense. It would have a lot of searching. I will also implement this. Thanks! — user1872912, Dec 03 '12 at 22:29
I would but I am new here and it doesn't let me yet, sorry :(. — user1872912, Dec 03 '12 at 22:37

Why doesn't thins Boggle Solver work?

2 Answers2