Print all the words in a 3x3 matrix 'c','b','k' ..... 'd','a','l' ...... 'g','t','i' . words can be found horizontally, vertically and diagonally (reverse/straight order).

/*
      An alphabet can be used only in one of the word.
      If any cell of matrix constitutes to any word, I have replaced the character with a '*'
*/

      #include <iostream>
      #include <sstream>
    
      using namespace std;
      const int DIM = 3;
      const int MAXNEIGHBOURS = 8;
      int displacement[8][2] = {{-1,-1},{0,-1},{1,-1},{1,0},{-1,1},{0,1},{-1,1},{-1,0}};
      char matrix[DIM][DIM] = {{'c','a','t'},{'a','j','i'},{'t','n','o'}};
      void displayMatrix();
    
      bool isValid(int row, int col)
      {
           if(row<0 || col <0 || row >= DIM || col >= DIM)
               return false;
           if(matrix[row][col] == '*')
               return false;
           return true;
      }
    
      bool solveMatrix(int row,int col, string word)
      {
           if(word.compare("*") ==0)
               return false;
           if(dictionary.search(word))
           {
               cout<<"\n"<<word;
               matrix[row][col] = '*';
               return true;
           }
           for(int i=0; i<MAXNEIGHBOURS ; i++)
           {
               int newRow = row + displacement[i][0];
               int newCol = col + displacement[i][1];
               char originalCharacter = matrix[row][col];
               matrix[row][col] = '*';
               if(isValid(newRow,newCol))
               {
                    if(solveMatrix(newRow,newCol,word+matrix[newRow][newCol]))
                        return true;
               }
               matrix[row][col] = originalCharacter;
           }
           return false;
      }
    
      string toString(char ch)
      {
          stringstream ss;
          string s;
          ss<<ch;
          ss>>s;
          return s;
      }
    
    
      int main()
      {
          dictionary.insert("hello");
          dictionary.insert("cat");
          dictionary.insert("in");
          dictionary.insert("no");
          dictionary.insert("at");
          for(int i=0; i<DIM; i++)
              for(int j=0; j<DIM; j++)
                  solveMatrix(i,j,toString(matrix[i][j]));
          cout<<endl;
          system("pause");
      }

/*
      I have used TRIE to store dictionary below is the implentation of it.
*/

      class TRIENode
      {
      public:
             bool word;
             int prefixCount;
             TRIENode *child[26];
    
             TRIENode()
             {
                  word = false;
                  prefixCount = 0;
                  for(int i=0; i<26; i++)
                      child[i] = NULL;
             }
            
             bool isWord()
             {
                 return word;
             }
      };
    
      class TRIE
      {
      private:
             TRIENode *headNode;
      public:
             TRIE()
             {
                 headNode = new TRIENode();
             }
            
             void insert(string w)
             {
                 TRIENode *ptr = headNode;
                 ptr->prefixCount++;
                 for(int i=0; i<w.length(); i++)
                 {
                     int index = w[i] - int('a');
                     if(ptr->child[index] ==NULL)
                     {
                          ptr->child[index] = new TRIENode();
                     }
                     ptr->child[index]->prefixCount++;
                     ptr = ptr->child[index];
                 }
                 ptr->word = true;
             }
            
             bool search(string str)
             {
                  TRIENode *ptr = headNode;
                  for(int i=0; i<str.length(); i++)
                  {
                      int index = str[i] - 'a';
                      if(ptr->child[index] == NULL)
                          return false;
                      ptr = ptr->child[index];
                  }
                  if(ptr->isWord())
                       return true;
                  return false;
             }
      }dictionary;