public class BoogleWords {
public static void main(String[] args) {
char[][] arr = { { 'A','B','C','E' },
{ 'S','F','C','S' },
{ 'A','D','E','E' } };
List<String> wordsList = Arrays.asList("ABCCED","SEE",
"ABCB","abcfedghi","aeifc", "eifh", "jagga", "bagga");
solveBoogle(arr, wordsList);
}
private static void solveBoogle(char[][] arr, List<String> wordsList) {
int[] xPath = { 0, -1, -1, 1, 1, 1, 0, -1, 0 };
int[] yPath = { 0, 0, 1, 1, 0, -1, -1, -1, 1 };
boolean[][] visited = new boolean[arr.length][arr[0].length];
if (!solveBGUtil(arr, wordsList, "", visited, 0, 0, xPath, yPath)) {
System.out.println("invalid");
return;
}
return;
}
private static boolean solveBGUtil(char[][] arr, List<String> wordsList,
String word, boolean[][] visited, int xPathRow,
int yPathCol, int[] xPath, int[] yPath) {
// System.out.println(word);
if (wordsList.contains(word)) {
System.out.println(word);
return true;
}
if (arr.length * arr.length == word.length()) {
return true;
}
boolean result = false;
for (int i = 0; i < xPath.length; i++) {
int rowNew = xPathRow + xPath[i];
int colNew = yPathCol + yPath[i];
if (isValid(rowNew, colNew, visited, arr.length)) {
visited[rowNew][colNew] = true;
result = solveBGUtil(arr, wordsList, word + arr[rowNew][colNew],
visited, rowNew, colNew, xPath, yPath) || result;
visited[rowNew][colNew] = false;
}
}
return result;
}
private static boolean isValid(int rowNew, int colNew, boolean[][] visited, int n) {
return rowNew >= 0 && rowNew < n &&
colNew >= 0 && colNew < n &&
visited[rowNew][colNew] == false;
}
}