## Problem: Word Boggle

*Difficulty: Medium

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'}};

Output:  Following words of dictionary are present
GEEKS, QUIZ

```

Input:
The first line of input contains an integer T denoting the no of test cases . Then T test cases follow. Each test case contains an integer x denoting the no of words in the dictionary. Then in the next line are x space separated strings denoting the contents of the dictinory. In the next line are two integers N and M denoting the size of the boggle. The last line of each test case contains NxM space separated values of the boggle.

Output:
For each test case in a new line print the space separated sorted distinct words of the dictionary which could be formed from the boggle. If no word can be formed print -1.

Constraints:
1<=T<=10
1<=x<=10
1<=n,m<=7

Example:
Input:

1
4
GEEKS FOR QUIZ GO
3 3
G I Z U E K Q S E

Output:
GEEKS QUIZ

*Approach: This problem is almost the same with this.
The mechanism gonna be used here is back tracking. There are only two main parts in the algorithm:

• With each cell in boggle matrix (two for loops)
• Check all possible words that can be generated with that cell
• While generating, if a generated word can be found in dictionary, add to result
• if the length of generated word equal the length of longest word in dictionary, return (base case)
• After getting all words, put them into a set to eliminate duplicate words, then sorted them alphabetically before output

Suppose max_level is the length of longest word in dictionary, as soon as the length of a generated word exceeds max_level, we return. Why? Because if we still continue generating, there is no word will match anything in dictionary.

Implementation: Python 2.7

```from __future__ import print_function

def generate_words(x, y, dictionary, boggle, visited_cells, level, max_level, result, word):
visited_cells.append((x, y))
word += boggle[x][y]
#print word
if word in dictionary:
result.append(word)
eight_directions = ((x+1, y), (x-1, y), (x, y+1), (x, y-1),
(x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1))
eight_directions = [(new_x,new_y) for new_x,new_y in eight_directions
if in_bound(new_x, new_y, boggle) and (new_x, new_y) not in visited_cells]
if level > max_level:
return
for new_x, new_y in eight_directions:
generate_words(new_x, new_y, dictionary, boggle,
visited_cells, level+1, max_level, result, word)
visited_cells.pop()

def find_all_possible_words(dictionary, boggle):
max_level = get_max_level(dictionary)
overall_result = []
for x in xrange(len(boggle)):
for y in xrange(len(boggle[x])):
result = []
visited_cells = []
level = 0
word = ""
generate_words(x, y, dictionary, boggle, visited_cells, level, max_level, result, word)
if result:
overall_result.extend(result)
overall_result = set(overall_result)
overall_result = list(sorted(overall_result))
if overall_result:
print(*overall_result, sep=" ")
else:
print(-1)

def get_max_level(dictionary):
return max(len(x) for x in dictionary)

def in_bound(x, y, boggle):
return (x >= 0 and x < len(boggle)) and (y >= 0 and y < (len(boggle[0])))

if __name__ == '__main__':
t = input()
for _ in range(t):
n = input()
dictionary = raw_input().strip().split()
n, m = map(int, raw_input().strip().split())
boggle = []
temp = raw_input().strip().split()
for i in range(0, len(temp), m):
boggle.append(temp[i:i+m])
#print(dictionary)
#print(boggle)
find_all_possible_words(dictionary, boggle)
```