Algotree > Algorithms > Backtracking > Boggle

Boggle

Word game Boggle implemented using Depth First Search (DFS) algorithm

Note
This approach uses DFS to form all possible words for searching, which turns out to be quite inefficient for larger ( N > 4 ) N X N boards.
For larger boards the search space (N X N)! becomes huge since we can’t predict if a substring can form a word going further. Also, the recursion is limited by the depth of the stack and cannot work for larger grids.
A better approach is to terminate the search if a substring cannot possibly form a word going further. i.e If a string is not the prefix of a word present in the search list, it need not be appended with other characters.

The purpose of listing the below approach was only to demonstrate where and how the DFS can be used. An efficient approach is using DFS & Tries.

DFS_Boggle

C++ : Boggle word search using Depth First Search (DFS) algorithm.

#include<iostream>
#include<vector>
#include<set>
#include<string>

using namespace std;

class Boggle {

    private:

        vector<vector<char>> grid;
        vector<vector<bool>> visited;
        set<string> wordlist;
        string current_str;

    public:

        Boggle() {}

        Boggle(vector<vector<char>> arg_grid, set<string> arg_wordlist) {
            grid = arg_grid;
            wordlist = arg_wordlist;
            visited.resize(grid.size());

            for (auto& v: visited)
                v.resize(grid[0].size());

            current_str = "";
        }

        void SearchWord(int row, int col) {

            if (wordlist.find(current_str) != wordlist.end()){
                cout << "Found : " << current_str << endl;
            } else {
                // Visit all the eight characters from top and bottom row and left and right column.
                for (int r = row-1; r <= row+1; r++) {
                    for (int c = col-1; c <= col+1; c++) {
                        if (r >= 0 and r < grid.size() and c >= 0 and c < grid[0].size()
                            and visited[r][c] == false) {
                            // C++11 Append character to the string.
                            visited[r][c] = true;
                            current_str.push_back(grid[r][c]);
                            SearchWord(r, c);
                            // C++11 Erase last character from the string.
                            current_str.pop_back();
                            visited[r][c] = false;
                        }
                    }
                }
            }
        }

        // Search if a word can be formed from every character in a grid.
        void TraverseGrid() {
            for (int row = 0; row < grid.size(); row++) {
                for (int col = 0; col < grid[0].size(); col++) {
                    visited[row][col] = true;
                    current_str.push_back(grid[row][col]);
                    SearchWord(row, col);
                    visited[row][col] = false;
                    current_str.pop_back();
                }
            }
        }
};

int main()
{
    // C++11 Initialize two dimensional vector 
    vector<vector<char>> grid {{ 'A', 'L', 'G' },
                               { 'T', 'E', 'O' },
                               { 'E', 'R', 'T' },
                               { 'O', 'C', 'K' }};

    set<string> wordlist;
    // Search if the below words exist in the boggle letter grid.
    wordlist.insert("ALGOTREE");
    wordlist.insert("ROCK");
    wordlist.insert("LEGO");
    wordlist.insert("DUGEE");
    wordlist.insert("ATE");
    wordlist.insert("TALE");
    wordlist.insert("NODDY");

    Boggle b(grid, wordlist);
    b.TraverseGrid();

    return 0;
}

Output

Found : ALGOTREE
Found : ALGOTREE
Found : ATE
Found : ATE
Found : LEGO
Found : TALE
Found : ROCK