Boggle Game Solver or Word Search in 2D Array or MXN Matrix by using DFS algorithm

This is one of the most important problem that every programmer should know. Specially who target for the top notch companies like bla..bla...bla.
In this post , lets focus on simple but less efficient approach to solve this problem. Before we start lets understand the problem.
Problem: Given a 2D array or a MXN matrix and a given dictionary, find all possible words made of combining characters of the matrix that belong to the given matrix where:
1) Each cell represents a character
2) A valid word must be composed by following a sequence of adjacent dice—two dice are adjacent if they are horizontal, vertical, or diagonal neighbors.
3) A valid word can use each cell at most once.
4) A valid word must be in the given dictionary.

                                                    DATES (invalid—cell 'D' and 'A' are not adjacent)

                                                   PINES(valid)

                                                  PINS (valid)
 

                                                    PINT (invalid—path between 'N' & 'T' not sequential)

                          SID (invalid—word not in dictionary)

 

TEPEE

                                                      (invalid—cell 'P' used more than once)

Courtesy: Images from stanford

There is a sample DFS implementation to solve this kind of problem as below:

import java.util.HashSet;
import java.util.Set;

/**
 * @author Sujeet Kumar (mrsujeet@gmail.com) It prints out all strings that can
 *         be formed by moving left, right, up, down, or diagonally and exist in
 *         a given dictionary , without repeating any cell. Assumes words are
 *         comprised of lower case letters. Currently prints words as many times
 *         as they appear, not just once. *
 */

public class BoggleGame {

    /* A sample 4X4 board/2D matrix */
    private static char[][] board = { { 's', 'a', 's', 'g' },
                                      { 'a', 'u', 't', 'h' },
                                      { 'r', 't', 'j', 'e' },
                                      { 'k', 'a', 'h', 'e' }
                                    };

    /* A sample dictionary which contains unique collection of words */
    private static Set dictionary = new HashSet();

    private static boolean[][] visited = new boolean[board.length][board[0].length];

    public static void main(String[] arg) {
        dictionary.add("sujeet");
        dictionary.add("sarthak");
        findWords();

    }

    // show all words, starting from each possible starting place
    private static void findWords() {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                StringBuffer buffer = new StringBuffer();
                dfs(i, j, buffer);
            }

        }

    }

    // run depth first search starting at cell (i, j)
    private static void dfs(int i, int j, StringBuffer buffer) {
        /*
         * base case: just return in recursive call when index goes out of the
         * size of matrix dimension
         */
        if (i < 0 || j < 0 || i > board.length - 1 || j > board[i].length - 1) {
            return;
        }

        /*
         * base case: to return in recursive call when given cell is already
         * visited in a given string of word
         */
        if (visited[i][j] == true) { // can't visit a cell more than once
            return;
        }

        // not to allow a cell to reuse
        visited[i][j] = true;

        // combining cell character with other visited cells characters to form
        // word a potential word which may exist in dictionary
        buffer.append(board[i][j]);

        // found a word in dictionary. Print it.
        if (dictionary.contains(buffer.toString())) {
            System.out.println(buffer);
        }

        /*
         * consider all neighbors.For a given cell considering all adjacent
         * cells in horizontal, vertical and diagonal direction
         */
        for (int k = i - 1; k <= i + 1; k++) {
            for (int l = j - 1; l <= j + 1; l++) {
                dfs(k, l, buffer);

            }

        }
        buffer.deleteCharAt(buffer.length() - 1);
        visited[i][j] = false;
    }

}


Complexity of this algo is MxNxW.

Thanks for reading...