Boggle ( Find all possible words in a board of characters ) | Set 1 | C ++ program for Boggle game ; Let the given dictionary be following ; 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 . ; Linearly search all words ; A recursive function to print all words present on boggle ; Mark current cell as visited and append current character to str ; If str is present in dictionary , then print it ; Traverse 8 adjacent cells of boggle [ i ] [ j ] ; Erase current character from string and mark visited of current cell as false ; Prints all words present in dictionary . ; Mark all characters as not visited ; Initialize current string ; Consider every character and look for all words starting with this character ; Driver program to test above function
#include <cstring> NEW_LINE #include <iostream> NEW_LINE using namespace std ; #define M  3 NEW_LINE #define N  3 NEW_LINE string dictionary [ ] = { " GEEKS " , " FOR " , " QUIZ " , " GO " } ; int n = sizeof ( dictionary ) / sizeof ( dictionary [ 0 ] ) ; bool isWord ( string & str ) { for ( int i = 0 ; i < n ; i ++ ) if ( str . compare ( dictionary [ i ] ) == 0 ) return true ; return false ; } void findWordsUtil ( char boggle [ M ] [ N ] , bool visited [ M ] [ N ] , int i , int j , string & str ) { visited [ i ] [ j ] = true ; str = str + boggle [ i ] [ j ] ; if ( isWord ( str ) ) cout << str << endl ; 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 ) ; str . erase ( str . length ( ) - 1 ) ; visited [ i ] [ j ] = false ; } void findWords ( char boggle [ M ] [ N ] ) { bool visited [ M ] [ N ] = { { false } } ; string str = " " ; for ( int i = 0 ; i < M ; i ++ ) for ( int j = 0 ; j < N ; j ++ ) findWordsUtil ( boggle , visited , i , j , str ) ; } int main ( ) { char boggle [ M ] [ N ] = { { ' G ' , ' I ' , ' Z ' } , { ' U ' , ' E ' , ' K ' } , { ' Q ' , ' S ' , ' E ' } } ; cout << " Following ▁ words ▁ of ▁ dictionary ▁ are ▁ present STRNEWLINE " ; findWords ( boggle ) ; return 0 ; }