Boggle (Find all possible words in a board of characters) | Set 1

// C# program for Boggle game
using System;
using System.Collections.Generic;

class GFG 
{
    // Let the given dictionary be following
    static readonly String []dictionary = { "GEEKS", "FOR", 
                                            "QUIZ", "GUQ", "EE" };
    static readonly int n = dictionary.Length;
    static readonly int M = 3, N = 3;

    // A given function to check if a given string 
    // is present in dictionary. The implementation is 
    // naive for simplicity. As per the question 
    // dictionary is given to us.
    static bool isWord(String str)
    {
        // Linearly search all words
        for (int i = 0; i < n; i++)
            if (str.Equals(dictionary[i]))
                return true;
        return false;
    }

    // A recursive function to print all words present on boggle
    static void findWordsUtil(char [,]boggle, bool [,]visited, 
                              int i, int j, String str)
    {
        // Mark current cell as visited and
        // append current character to str
        visited[i, j] = true;
        str = str + boggle[i, j];

        // If str is present in dictionary,
        // then print it
        if (isWord(str))
            Console.WriteLine(str);

        // Traverse 8 adjacent cells of boggle[i,j]
        for (int row = i - 1; row <= i + 1 && row < M; row++)
            for (int col = j - 1; col <= j + 1 && col < N; col++)
                if (row >= 0 && col >= 0 && !visited[row, col])
                    findWordsUtil(boggle, visited, row, col, str);

        // Erase current character from string and 
        // mark visited of current cell as false
        str = "" + str[str.Length - 1];
        visited[i, j] = false;
    }

    // Prints all words present in dictionary.
    static void findWords(char [,]boggle)
    {
        // Mark all characters as not visited
        bool [,]visited = new bool[M, N];

        // Initialize current string
        String str = "";

        // Consider every character and look for all words
        // starting with this character
        for (int i = 0; i < M; i++)
            for (int j = 0; j < N; j++)
                findWordsUtil(boggle, visited, i, j, str);
    }

    // Driver Code
    public static void Main(String []args)
    {
        char [,]boggle = { { 'G', 'I', 'Z' },
                           { 'U', 'E', 'K' },
                           { 'Q', 'S', 'E' } };

        Console.WriteLine("Following words of " +  
                          "dictionary are present");
        findWords(boggle);
    }
}

// This code is contributed by PrinciRaj1992

// C# program for Boggle game
using System;
using System.Collections.Generic;

class Boggle
{
static int M = 3;
static int N = 3;
static bool dfs(char[][] board, string s, int i, int j, int n, int m, int idx)
{

    if (i < 0 || i >= n || j < 0 || j >= m)
    {
        return false;
    }

    if (s[idx] != board[i][j])
    {
        return false;
    }
    if (idx == s.Length - 1)
    {
        return true;
    }

    char temp = board[i][j];
    board[i][j] = '*';

    bool a = dfs(board, s, i, j + 1, n, m, idx + 1);
    bool b = dfs(board, s, i, j - 1, n, m, idx + 1);
    bool c = dfs(board, s, i + 1, j, n, m, idx + 1);
    bool d = dfs(board, s, i - 1, j, n, m, idx + 1);
    bool e = dfs(board, s, i + 1, j + 1, n, m, idx + 1);
    bool f = dfs(board, s, i - 1, j + 1, n, m, idx + 1);
    bool g = dfs(board, s, i + 1, j - 1, n, m, idx + 1);
    bool h = dfs(board, s, i - 1, j - 1, n, m, idx + 1);

    board[i][j] = temp;
    return a || b || c || e || f || g || h || d;


}
static void wordBoggle(char[][] board, string[] dictionary)
{
    int n = board.Length;
    int m = board[0].Length;
    List<string> ans = new List<string>();
    HashSet<string> store = new HashSet<string>();
    for (int i = 0; i < dictionary.Length; i++)
    {
        string s = dictionary[i];
        int l = s.Length;
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < m; k++)
            {
                if (dfs(board, s, j, k, n, m, 0))
                {
                    store.Add(s);
                }
            }
        }
    }

    foreach (string i in store)
    {
        Console.WriteLine(i);
    }

    return;

}

// Driver program to test above function
public static void Main()
{
    char[][] boggle = new char[][] {
    new char[] { 'G', 'I', 'Z' },
    new char[] { 'U', 'E', 'K' },
    new char[] { 'Q', 'S', 'E' }
    };
    // Let the given dictionary be following
    string[] dictionary = new string[] {"GEEKS", "FOR", "QUIZ", "GO"};
Console.WriteLine("Following words of dictionary are present");  
wordBoggle(boggle, dictionary);
}
}

//This code is contributed by shivamsharma215