1. #1
    High Overlord Nemean's Avatar
    Join Date
    Jun 2010
    Location
    Auburn, Al
    Posts
    126

    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
    CPU: Intel i5-2500k MB: ASRock Z77 Extreme
    GPU: Asus HD 7850 RAM: Mushkin Blackline 8GB
    HDD: WD Caviar Black 1TB PSU: OCZ 500W CASE: Cooler Master HAF 922

  2. #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.
    Kuroiwolf - 90 Brewmaster Monk
    Youtube Account Twitch TV
    Computer: Intel I7-3770k @ 4.5GHz | 16GB 1600MHz DDR3 RAM | AMD 7970 GHz @ 1200/1600 | ASUS Z77-V PRO Mobo|

  3. #3
    Brewmaster Biernot's Avatar
    Join Date
    Mar 2009
    Location
    Germany
    Posts
    1,296
    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.

  4. #4
    Bloodsail Admiral Twoddle's Avatar
    Join Date
    Feb 2011
    Location
    UK
    Posts
    1,027
    Answering your other thread:

    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)
              machineWords.add(prefix);
    
    // looks at all adjacent 
    			
        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. #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)
            machineWords.add(prefix);
    
        //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);
    Last edited by yurano; 2012-11-11 at 11:59 PM.

  6. #6
    Bloodsail Admiral Twoddle's Avatar
    Join Date
    Feb 2011
    Location
    UK
    Posts
    1,027
    Quote Originally Posted by yurano View Post
    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. #7
    Quote Originally Posted by Twoddle View Post
    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. #8
    High Overlord Nemean's Avatar
    Join Date
    Jun 2010
    Location
    Auburn, Al
    Posts
    126
    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.
    CPU: Intel i5-2500k MB: ASRock Z77 Extreme
    GPU: Asus HD 7850 RAM: Mushkin Blackline 8GB
    HDD: WD Caviar Black 1TB PSU: OCZ 500W CASE: Cooler Master HAF 922

  9. #9
    Quote Originally Posted by Nemean View Post
    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.
    Last edited by yurano; 2012-11-12 at 02:38 AM.

  10. #10
    High Overlord Nemean's Avatar
    Join Date
    Jun 2010
    Location
    Auburn, Al
    Posts
    126
    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
    CPU: Intel i5-2500k MB: ASRock Z77 Extreme
    GPU: Asus HD 7850 RAM: Mushkin Blackline 8GB
    HDD: WD Caviar Black 1TB PSU: OCZ 500W CASE: Cooler Master HAF 922

  11. #11
    Bloodsail Admiral Twoddle's Avatar
    Join Date
    Feb 2011
    Location
    UK
    Posts
    1,027
    Quote Originally Posted by yurano View Post
    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. #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);
    Last edited by yurano; 2012-11-12 at 02:52 AM.

  13. #13
    High Overlord Nemean's Avatar
    Join Date
    Jun 2010
    Location
    Auburn, Al
    Posts
    126
    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.
    CPU: Intel i5-2500k MB: ASRock Z77 Extreme
    GPU: Asus HD 7850 RAM: Mushkin Blackline 8GB
    HDD: WD Caviar Black 1TB PSU: OCZ 500W CASE: Cooler Master HAF 922

  14. #14
    Bloodsail Admiral Twoddle's Avatar
    Join Date
    Feb 2011
    Location
    UK
    Posts
    1,027
    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. #15
    High Overlord Nemean's Avatar
    Join Date
    Jun 2010
    Location
    Auburn, Al
    Posts
    126
    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.
    CPU: Intel i5-2500k MB: ASRock Z77 Extreme
    GPU: Asus HD 7850 RAM: Mushkin Blackline 8GB
    HDD: WD Caviar Black 1TB PSU: OCZ 500W CASE: Cooler Master HAF 922

Posting Permissions

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