How to find list of possible words from a letter matrix [Boggle Solver]

https://xmruibi.gitbooks.io/interview-preparation-notes/content/Algorithm/Backtracking/BoggleGame.html

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.

• DFS on character board to do backtracking.
• Searching the character for 8 directions.
• Mark the visited position by a boolean board (Takes O() space)

    public List<String> findWords(HashSet<String> dict, char[][] board) {
        List<String> res = new ArrayList<>();
        boolean[][] visited = new boolean[board.length][board[0].length];
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                findUtil(res, dict, board, visited, "", i, j);
            }
        }
        return res;
    }

    private void findUtil(List<String> res, HashSet<String> dict, char[][] board, boolean[][] visited, String cur, int x, int y) {
        visited[x][y] = true;
        cur += board[x][y];

        if(dict.contains(cur)) {
            res.add(cur);
            dict.remvoe(cur);
            return;
        }
        // 8 - direction
        int[] xs = {1,1,1,0,0,-1,-1,-1};
        int[] ys = {1,-1,0,1,-1,0,1,-1};
        for(int i = 0; i < 8; i++) {
            int nx = xs[i] + x;
            int ny = ys[i] + y;
            if(nx >= 0 && nx < board.length && ny >= 0 && ny < board[nx].length && !visited[nx][ny])
                findUtil(res, dict, board, visited, cur, nx, ny);
        }
        visited[x][y] = false;
        cur = cur.substring(0, cur.length() - 1);
    }

Solving the Boggle Game - Recursion, Prefix Tree, and Dynamic Programming
Third and Final Solution - No search space + Dynamic Programming:
It turns out, we can use a nifty dynamic programming technique to quickly check whether a word (from the dictionary in this case) can be constructed from the board or not!

How to find list of possible words from a letter matrix [Boggle Solver]
Not efficient:
Use

https://fragmaticprogrammer.wordpress.com/2012/07/02/boggle-solver-2/

Java Solution:
Use BFS
https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/BoggleSolver.java

http://codereview.stackexchange.com/questions/33045/boggle-solver-in-java

http://www.bowdoin.edu/~ltoma/teaching/cs210/spring08/Labs/Lab5/Boggle/