in c++, the Game of Boggle: The object of game Boggle is to find as many words a

Question

in c++, the Game of Boggle: The object of game Boggle is to find as many words as possible in a k by k grid of letters. Words may be formed from any sequence of 3 or more adjacent letters in the grid. The letters may be joined together horizontally or vertically or diagonally. No position in the grid may be used more than once within any one word. You may not wrap around the grid. The first line of the input is the integer k, followed by k lines with k characters per line.

For instance, a sample grid might look like:

4

dcvf

ceta

natc

ftag

Valid words that can be traced by this board involve fact, cat, face etc.. What your Program Should Do:Your program should be implemented in C++ . Your program should read the dictionary from the file dictionary.txt.( https://raw.githubusercontent.com/dwyl/english-words/master/words.txt ) this file can be used as dictionary.

First of all, write a function that reads in the board and prints it out. Your program should read the Boggle board in the format specified above (the first line specifies the integer k, and the following k lines give the board) from a file board.txt( You can set your own file). Your program then read the words from dictionary.txt and store in some data structure like array. Finally, you should print all the words that it finds in the grid and print them out. Hint: using recursion, recursive backtracking (similar to Sudoku)

Explanation / Answer

// C++ program for Boggle game
#include<iostream>
#include<cstring>
using namespace std;

#define M 3
#define N 3

// Let the given dictionary be following
string dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};
int n = sizeof(dictionary)/sizeof(dictionary[0]);

// A given function to check if a given string is present in
// dictionary. The implementation is naive for simplicity. As
// per the question dictionary is givem to us.
bool isWord(string &str)
{
    // Linearly search all words
    for (int i=0; i<n; i++)
        if (str.compare(dictionary[i]) == 0)
          return true;
    return false;
}

// A recursive function to print all words present on boggle
void findWordsUtil(char boggle[M][N], bool visited[M][N], int i,
                   int j, string &str)
{
    // Mark current cell as visited and append current character
    // to str
    visited[i][j] = true;
    str = str + boggle[i][j];

    // If str is present in dictionary, then print it
    if (isWord(str))
        cout << str << endl;

    // Traverse 8 adjacent cells of boggle[i][j]
    for (int row=i-1; row<=i+1 && row<M; row++)
      for (int col=j-1; col<=j+1 && col<N; col++)
        if (row>=0 && col>=0 && !visited[row][col])
          findWordsUtil(boggle,visited, row, col, str);

    // Erase current character from string and mark visited
    // of current cell as false
    str.erase(str.length()-1);
    visited[i][j] = false;
}

// Prints all words present in dictionary.
void findWords(char boggle[M][N])
{
    // Mark all characters as not visited
    bool visited[M][N] = {{false}};

    // Initialize current string
    string str = "";

    // Consider every character and look for all words
    // starting with this character
    for (int i=0; i<M; i++)
       for (int j=0; j<N; j++)
             findWordsUtil(boggle, visited, i, j, str);
}

// Driver program to test above function
int main()
{
    char boggle[M][N] = {{'G','I','Z'},
                         {'U','E','K'},
                         {'Q','S','E'}};

    cout << "Following words of dictionary are present ";
    findWords(boggle);
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.