This is an efficient Boggle solver written in Java. The efficiency comes from the use of HashSets which have an O(c) contains method. Recursion is used to solve the puzzle.
I have seen very inefficient Boggle solvers on the internet. One programmer said that his program could not complete the list before the 3 min. time ran out on the Boggle game on Pogo. Another had a long delay after I entered the board. At least 20 seconds for each solve.
As I have said in class, after you learn basic coding, you need to learn efficiency. Knowing what language to use makes you more efficient. Knowing algorithmic analysis (Big "O" notation) makes you more efficient.
Java is inefficient for number crunching compared to C and C++ but its ease of developing a GUI makes it attractive. Remember that Java is an interpreted language and runs about 20 times slower than C and C++. (Java has traded an .exe file for the .class file interpreted by the JVM and the stunning property of being cross platform compatible) In this case, I felt that the loss of efficiency using Java was offset by the ease of making a GUI, especially after I coded and tested the run time.
I considered an ArrayList with a binary search to match possible words with the dictionary, but thought "That is O(log(N)) efficiency". I then though of a HashSet and thought, "Since the words will be pulled out by a simple hash of the string input, it should be O(Constant)". After looking at the Java library site I confirmed that .contains() is indeed O(Constant) - the best efficiency you can get in an algorithm.
After obtaining such efficiency with the word database, I was able to use a relatively inefficient recursive algorithm to search the board for words and obtained solves with times like 0.2 seconds per solve on my antique computer at home. (It's at least 2 years old)
My Boggle database consists of over 272,000 words. This means that for each possible word (630840 possible words limiting the longest to 8 characters long) the recursive algorithm finds, those 630840 words must be checked against 272,000 words. Log base 2 of 272,000 is 17. That means I would have to do 17 times more work using the O(log(N)) algorithm. 17*.2 seconds = 3.4 seconds, which is still good but there would be a noticeable delay using that algorithm.
There is work to do for the ambitious. The GridBag layout is disconcerting when it jumps around. The lack of color is bland. This could be converted to an applet. You could add user input to the grid instead of just to the text box.
To run the solver, download the zip below and unpack it. Click on the Boggle.jar file to run. The source file and dictionary are included as Boggle.java and dict.txt respectively.
Boggle.zip source, jar, dictionary
*new* Added word length variable to allow for different maximum word lengths