GeeksForGeeks Boggle Solver : Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Reference :http://www.geeksforgeeks.org/boggle-find-possible-words-board-characters/

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,

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

Method 1 : Simple Backtracking
Solution in Java

package BoggleSolver;

import java.util.ArrayList;

public class Solution {

//Define all the static words at class level

static String [] dictionary = {"GEEKS","QUIZ","GO","FOR"};

static char boggle[][]   = {{'G','I','Z'},

{'U','E','K'},

{'Q','S','E'}}; 

static int NEIGHBOURS = 8;

static int [] neighbourY = {-1,0,1,-1,1,-1, 0, 1};

static int [] neighbourX = { 1,1,1, 0,0,-1,-1,-1};

static int nrows = boggle.length;

static int ncols = boggle[0].length;

//below function will search for the word in the dictionary

static boolean findWord(StringBuilder word)

{

for(int i =0;i<dictionary.length;i++)

{

if(word.toString().compareTo(dictionary[i])==0)

{

return true;

}

}

return false;

}

//below function will search for the word characters in the neighboring cells recursively 

static StringBuilder searchWord(int row,int col,StringBuilder word,int[][] visited)

{

visited[row][col] = 1;

word.append(boggle[row][col]);

//System.out.println(word);

if(findWord(word))

{

//System.out.println(word);

return word;

}

for(int nx = row-1;nx<=row+1&&nx<nrows;nx++)

{

for(int ny = col-1;ny<=col+1&&ny<ncols;ny++)

{

if(nx>=0 && ny>=0 && visited[nx][ny]==0)

{

  StringBuilder op = searchWord(nx,ny,word,visited);

  if(op.length()>0)

  {

  return op;

  }

}

}

}

//reset the visited array col and row number to zero i.e., make it unvisited

visited[row][col] = 0;

//decrease the word length by 1

word.setLength(word.length()-1);

    return new StringBuilder();

}

//below function will check if the row and col number is valid and it is not present in visited array

static boolean isValid(int row, int col, int nx, int ny,int[][] visited)

{

if((row+nx)>-1 && (row+nx)<boggle.length && (col+ny)>-1 && (col+ny)< boggle[0].length  && visited[row+nx][col+ny]==0)

{

return true;

}

else

{

return false;

}

}

// loop through the entire boggle to find the all related words that are contained in Dictionary

static String[] findWords()

{

int [][] visited = new int[nrows][ncols];

ArrayList<StringBuilder> list = new ArrayList<StringBuilder>();

for(int i =0;i<nrows;i++)

{

for(int j =0;j<ncols;j++)

{

StringBuilder output = searchWord(i,j,new StringBuilder(),visited);

if(output.length()>0)

{

list.add(output);

}

}

}

String[] res = null;

if(!list.isEmpty())

{

    res= new String[list.size()];

for(int i =0;i<list.size();i++)

{

res[i] = list.get(i).toString();

}

return res;

}

else

{

return null;

}

}

public static void main(String[] args) {

// TODO Auto-generated method stub

String[] res = findWords();

for(int i =0;i<res.length;i++)

{

System.out.println(res[i]);

}

}

}