Java Word Search Solver Design Approach

Question

I am writing a program that is a word search solver and was curious if there was a better approach than what I was taking. The program contains a grid of characters that are suppose to be the puzzle followed by a line break and words to be located in the matrix.

My question is that in locating for the beginning and ending characters of each string would it be better to just strong arm it through the puzzle with nested loops for each direction or could this process be streamlined using some sort of straight line detection algorithm?

The Words can be horizontal, vertical or diagonal and the reverse of each.

Really what I am looking to do is plot the beginning and ending points of a char array (The Word) inside the 2d char array (Puzzle)

Example of puzzle
HGAMONIHRA
AOMOKAWONS
NFROLBOBDN
ARFSIHCAGE
LNIEEWONOK
GOLFUNDTHC
KOCATAOHBI
AMRERCGANH
SLGFAMALLC
ALLIGATORX

HORSE
COW
RHINO
JABBERWOCKY
CAT
DOG
ALLIGATOR
CHICKEN
FROG
BANTHA
MOOSE
LLAMA

Assuming I use just a series of loops I am unsure of the best way to do that to check in all the directions. So far I just have it working searching the words horizontally

                boolean over = false;
                boolean foundit = false;
                String word = new String(letters);

                for (int i = 0; (i < puzzle.length) && (!over); i++) {
                    for (int j = 0; (j < puzzle[i].length) && (!over); j++) {

                        // Use (i,j) as the starting point.
                        foundit = true;

                        // Look through each letter in word
                        for (int k = 0; (k < letters.length) && (foundit); k++) {
                            if ((j + k >= puzzle[i].length)
                                    || (letters[k] != puzzle[i][j + k])) {
                                // It didn't Match
                                foundit = false;
                            }
                        }
                        // Success if we made it through all the characters
                        if (foundit) {
                            System.out.println(word + " found in row=" + i
                                    + " col=" + j);
                            over = true;
                        }

                    }
                }

                if (!foundit) {
                    System.out.println(word + " not found");
                }

Any Pointers on finding them vertically, diagonal and reverse?

Answer 1

Doing it brute force won't be terrible. You could use a faster algorithm, but the initial overhead might outweigh the benefits, so be sure to benchmark for a typical example.

You could try throwing the whole puzzle in a multi_hashmap where the letter is the key and the position is the value. This would make searching faster (O(1) for a lookup rather than O(n) to find the first letter), but you probably don't gain much since you have to traverse the whole puzzle to put it into the hashmap.

Brute force is pretty close to O(n*m) where n is the puzzle size and m is the number of hidden words. (I assume a constrained word length, say 20.)

Using the hashmap doesn't buy all that much. It's about O(n+m), but for smaller puzzles that's not much of a time difference. It's definitely better asymptotically, though. Do both and compare their times. That's the best way to know.