1. ## Boggle word solver

hello, im trying to figure out a way to be able to look at a boggle board (4x4 matrix) of letters and find every possible word that is in that matrix that follows the rules of boggle, can only use letters that are horizontal, vertical, or diagonal. each letter (dice) can only be used once. From what i have seen using prefix is the most efficient way along with using a trie data structure. I have managed to make a trie with a prefix method and another method to see if a word has been made. Im looking for some possible ideas to help me move toward a solution. I dont want the actual solution. My current code is available if needed.

here is an example boggle board:
Code:
```[Y, B, E, O]
[E, K, A, I]
[U, G, F, L]
[M, O, D, H]```
derp messed up the title, if a mod could change to boggle word solver

2. I'm not saying that this is the most efficient method, but this is how I would go about it;

First you'll need to distinguish the possible paths for words, e.g.

B -> E -> A -> K makes a square, where it doesn't join on one side.
F -> A - > I -> L is also another square, where it doesn't join on one side.

This uses a similar pattern, but starts at a different location.
You'll have to create a repeating method which uses all possible paths, which starts at different locations.

One way to optimize this would be search a preset dictionary for when you get two letters. E.g. Y -> K.
If there are no words which have Y -> K then move onto the next location.

3. Well it's been some time since i actively coded, but here would be a take from me:

Dictionary
Obviously you would need some kind of dictionary where you can look up, if a word is actually a genuine word.
As Yohassakura also pointed out, the dictionary should have some kind of feature where you can look up only parts of words to determine if there if even is a word with that kind of beginning letters. Else you would nearly always go to the full length of 16 letters.

Arranging the grid
For obvious reasons, you need a method to describe which letters are eligible from the current position in the grid. This also includes, which letters have already been used and as such are out already.
- obviously we have an array of the letters
- then we need an array to mark already used letter-positions.

Now comes the interesting part: How to discern, which letter is eligible? Two methods:

a. calculating via array position
If letters[x,y] is our grid, then all positions are available which have x-1 <= x_new <= x+1 and have y-1 <= y_new <= y+1

b. look-up tables
As we are dealing with "only" 16 positions in the letter array, then look-up-tables for each letter position might be the faster way (look-up tables are always faster, but depending on the array size, they very fast become memory heavy. And you need to create the tables first, which can be a huge time sink for larger arrays.).
So you just need to create 16 corresponding boolean tables were eligible positions are stored.
If you are using this method, you also wouldn't need to use a two-dimensional array, but a one-dimensional would be sufficient. (which would make the naming-scheme for the look-up table easier to handle)
Code:
```Your letter-"table"
[  0,  1,  2,  3,
4,  5,  6,  7,
8,  9, 10, 11,
12, 13, 14, 15 ]

eligible next-letter positions for letter 10:
[ 0, 0, 0, 0,
0, 1, 1, 1,
0, 1, 0, 1,
0, 1, 1, 1 ]

now imagine, we had started with letter 7, then our unused-letter table would be this:
[ 1, 1, 1, 1,
1, 1, 1, 0,
1, 1, 0, 1,
1, 1, 1, 1 ]

a simple multiplication with the next-letter table would give us the currently available next letters:
[ 0, 0, 0, 0,    [ 1, 1, 1, 1,    [ 0, 0, 0, 0,
0, 1, 1, 1,      1, 1, 1, 0,      0, 1, 1, 0,
0, 1, 0, 1,  *   1, 1, 0, 1,  =   0, 1, 0, 1,
0, 1, 1, 1 ]     1, 1, 1, 1 ]     0, 1, 1, 1 ]```
From that on, it is just a simple trial-and-error procedure to work through all possible word combinations.

Code:
```private void wordSearch(String prefix, int row, int col)
{
// checks to see if it is out of bounds
if (row < 0 || col < 0 || row >= size || col >= size)
return;

// see if the letter has been used yet
if (checkTable[row][col])
return;

// the letter has been visited
checkTable[row][col] = true;

//is the prefix in the dictionary
prefix = prefix + board.getLetter(row, col);
if (dictionary.contains(prefix) && prefix.length() > 2)

for (int i = -1; i <= 1; i++)
for (int j = -1; j <= 1; j++)
wordSearch(prefix, row + i, col + j);

checkTable[row][col] = false;
}```
Is that Java?

I just wrote your algorithm in C#, it does work but it will be very slow because dictionary.contains(prefix) is a huge bottleneck. You should rearrange this line to:

Code:
`if (prefix.length() > 2 && dictionary.contains(prefix))`
so that dictionary.contains doesn't get called unless prefix.Length is >2 but it's still very slow.

5. Simplest way (logically): Recursion

Here, I'm using your variables and function names.

I am using the boggleTable itself to check whether the position has already been traversed. By the way, you never reinitialize your 'checkTable' to false at termination of each wordSearch chain (aka when you hit the 'return' statement). Another method is to have your 'checkTable' passed through the recursive function like I have done with 'boggleTable'.

Code:
```private void wordSearch(String currentWord, int row, int col, char[size][size] boggleTable)
{
//Check out of bounds
if(row < 0 || col < 0 || row >= boggleTable.size|| col >= boggleTable[row].size)
return;

//Check if current letter used, we using a space to denote the letter has been used
if(char[row][col] = ' ')
return;

//Update Word, Update Table
currentWord = currentWord + boggleTable[row][col];
char[row][col] = ' ';

//Check current word
if (dictionary.contains(currentWord) && currentWord.length() > 2)

//Recursion
wordSearch(currentWord, row - 1, col - 1, boggleTable); //Top Left
wordSearch(currentWord, row - 1, col, boggleTable); //Top Mid
wordSearch(currentWord, row -1 , col + 1, boggleTable); //Top Right
wordSearch(currentWord, row, col - 1, boggleTable); //Left
wordSearch(currentWord, row, col + 1, boggleTable); //Right
wordSearch(currentWord, row + 1, col - 1, boggleTable); //Bottom Left
wordSearch(currentWord, row, col, boggleTable); //Bottom Mid
wordSearch(currentWord, row + 1, col + 1, boggleTable); //Bottom Right
}```

You would initialize this recursive function in the following way:

Code:
```char[size][size] originalTable = initializeTable();

wordSearch("", 0, 0, originalTable);```

6. Originally Posted by yurano
By the way, you never reinitialize your 'checkTable' to false at termination of each wordSearch chain (aka when you hit the 'return' statement)
It doesn't need to be reinitialized since it happens automatically, I've programmed his exact algorithm in C# and it works.

7. Originally Posted by Twoddle
It doesn't need to be reinitialized since it happens automatically, I've programmed his exact algorithm in C# and it works.
He's using his 'checkTable' to determine whether he's already traversed a node. If its never reinitialized to false at the end of a chain, it will traverse once then quit.

8. Yes its in java, and also i tried your solution yurano and it does not work. It sometimes says there is a word, but most of the time it says 0 words were found. Im using a trie structure for my dictionary, but that shouldnt matter.

9. Originally Posted by Nemean
Yes its in java, and also i tried your solution yurano and it does not work. It sometimes says there is a word, but most of the time it says 0 words were found. Im using a trie structure for my dictionary, but that shouldnt matter.
Did you test your dictionary function to make sure it works correctly? Your machineWords.add() function may also be at fault. Your recursion function seems to be right besides the reset of checkTable to all false whenever you hit a 'return'.

By the way, I forgot to change that line to machineWords.add(currentWord); instead of using 'prefix' as the variable.

10. Yeah, it works perfectly when i enter my own words.

---------- Post added 2012-11-11 at 08:36 PM ----------

even the prefix method of it works

11. Originally Posted by yurano
He's using his 'checkTable' to determine whether he's already traversed a node. If its never reinitialized to false at the end of a chain, it will traverse once then quit.
I hear you and I'm saying that given his algorithm reinitialization of checkTable is not required because after the chain it will always be false anyway. Try it. Maybe you didn't scroll down his code to see the last line.

12. Here might be a problem with the code. You need to call wordSearch() size*size or 16 times during the initialization. Basically you need to initialize a wordSearch() recursion tree for every node.

Code:
```char[size][size] originalTable = initializeTable();

for(int i = 0, i < size; i++)
for(int j = 0, j < size; j++)
wordSearch("", i, j, originalTable);```

13. Yeah that's what i have, but it still doesn't work. I also know there is a more efficient way to do it and has to do with hamiltonian path, but i have no clue how to implement it.

14. Not sure what IDE you're using but can't you put breakpoints at crtitical points in the code and step through line by line to see what's going wrong? Your algorithm works fine in my program and I copied it line for line.

15. I'm using jgrasp. But from what I remember it was exiting early I think. I'm at school right now, I'll check once I get back

---------- Post added 2012-11-12 at 05:42 PM ----------

I managed to figure out what was going wrong, and it was a stupid error on my part, i accidentally removed the checkTable[row][col] = false;. That was why it was being kicked out so fast, so once i added that, it worked like a charm. Thanks for the help.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•