# Boggle (Find all possible words in a board of characters) | Set 1

Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.

Example:

```Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};
boggle[][]   = {{'G','I','Z'},
{'U','E','K'},
{'Q','S','E'}};
isWord(str): returns true if str is present in dictionary
else false.

Output:  Following words of dictionary are present
GEEKS
QUIZ``` The idea is to consider every character as a starting character and find all words starting with it. All words starting from a character can be found using Depth First Traversal. We do depth first traversal starting from every cell. We keep track of visited cells to make sure that a cell is considered only once in a word.

 `// C++ program for Boggle game ` `#include ` `#include ` `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); ` ` `  `// 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 given to us. ` `bool` `isWord(string &str) ` `{ ` `    ``// Linearly search all words ` `    ``for` `(``int` `i=0; i=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

Output:

```Following words of dictionary are present
GEEKS
QUIZ ```

Note that the above solution may print the same word multiple times. For example, if we add “SEEK” to the dictionary, it is printed multiple times. To avoid this, we can use hashing to keep track of all printed words.

In below set 2, we have discussed Trie based optimized solution:
Boggle | Set 2 (Using Trie)

## tags:

Graph Algorithms-Backtracking DFS DFS Graph