Write a program to implement Boggle Game.

You are given a 4x4 matrix of letters and a dictionary, find all the valid words in the matrix. Following are the conditions

1. If a letter is used, it should not be used again in the same word search
2. The word path can be of any direction
3. There has to be a path of the letters forming the word( in other words all the letters in the word must have to adjacent to one another)
   Example:

D A T H
C G O A
S A T L
B E D G

Some of the Valid words are:
DATA, HALO, HALT, SAG, BEAT, TOTAL, GLOT, DAG

Not valid words:
DAGCD ( D cannot be used again)
DOG ( There is no path between letters)

Question 1:
This question sounds like word search ii, but in word search ii, the word path can only go through 4 directions: up, down, left, right. In this question, the path can go to any directions. How can we handle this situation?

Question 2:
Scalability follow up question:
what if we have a large number of words in dictionary, what if the matrix is extremely large, what should we do?

Thanks, guys.