Java Word Search Solver

This is a challenge up on Programming Praxis, however there are no Java solutions, and there are few Java implementations elsewhere on the internet.

Most of these implementations simply search the grid for the words that the user is supposed to find. This program finds ALL of the dictionary words that are in the word search puzzle, not just the ones that are supposed to be found. As a result the code is a bit lengthy; this is also due to the commenting.

EDIT: The dictionary file must be in alphabetical order, as Collections.binarySearch is used. The program used my Red-Black implementation yesterday but have removed this in favour of ArrayList so it now only requires the one file.

The source files and dictionary/puzzle files can be found here.

GitHub

Usage & Output:

Input file (lovatts 18x18):

11 11
B E I E L P I T L U M
R S P E C I A L M C D
R R U N C O M M O N A
S E A N A M E N D T S
E V T L D O T S I C S
G I F L U R A D F N O
N D F E A G Y D Y I R
A D E S U F N O C T T
R A T M O S A I C S E
T T E T A R A P S I D
S H E E T A I V E D R


The first two numbers represent the number of rows and the number of columns respectively. The rest of the file is the puzzle grid, with the characters separated by spaces. I could do it with no spaces but it makes the original file much more human-readable this way.

Command and output:

java WordSearch dictionary.txt lovatts18.txt 7

` A B C D E F G H I J K
----------------------
01 |B E I E L P I T L U M
02 |R S P E C I A L M C D
03 |R R U N C O M M O N A
04 |S E A N A M E N D T S
05 |E V T L D O T S I C S
06 |G I F L U R A D F N O
07 |N D F E A G Y D Y I R
08 |A D E S U F N O C T T
09 |R A T M O S A I C S E
10 |T T E T A R A P S I D
11 |S H E E T A I V E D R

Searching for words with 7 or more letters:

Found 14 words:

[K, 3 ] -> [K, 10] : ASSORTED
[I, 8 ] -> [C, 8 ] : CONFUSE
[I, 8 ] -> [B, 8 ] : CONFUSED
[J, 2 ] -> [C, 9 ] : CONTRAST
[J, 11] -> [D, 11] : DEVIATE
[K, 10] -> [C, 10] : DISPARATE
[J, 1

/**
     * A method that loads a dictionary text file into a tree structure
     * @param filename The dictionary file to load
     * @return The Red-Black tree containing the dictionary
     */
    private static ArrayList loadDict(String filename) {
        ArrayList dict = new ArrayList();
        try {
            BufferedReader in = new BufferedReader(
                    new FileReader(filename));
            String word;
            while( (word = in.readLine()) != null ) {
                dict.add(word);
            }
        } catch( IOException e ) {
            System.err.println("A file error occurred: " + filename );
            System.exit(1);
        }
        return dict;
    }

Your Javadoc is out of date. It still thinks that you are returning a tree.

As a general rule, you should return a List (the interface) rather than an ArrayList (the implementation). This will make it much easier to change the implementation in the future.

You are missing an

in.close();

in your try block.

I actually think that you are better off allowing the exception to create a stack trace and crash the program. While testing this, I was drawing the exception because the file was in the wrong place. Since you don't log the real error anywhere, I had to remove the try/catch block in order to get the error message. If you mark the method as throwing an IOException, it actually makes it easier to debug.

private static List loadDict(String filename) throws IOException {

Of course, if you do that, you need to mark main as throwing an exception as well.

I tried storing the dictionary in a trie, but it was slower and took more memory than your solution.

StackExchange Code Review Q#81790, answer score: 4