Feature #1: Search for a Single Word in the Boggle Grid

Description

For this project’s first feature, you are given a grid of letters, representing the Boggle grid, and a word to search inside that grid. The input is twenty-five alphabets arranged in a 5x5 grid. In this variation of the Boggle game, there are the following rules:

• Words can be constructed from the letters in sequentially adjacent cells.
• These adjacent cells can be horizontal or vertical neighbors only. Diagonally opposite dice are not considered adjacent.
• A cell can only be part of one word.

Take a look at the following illustration to better understand how to find words in the Boggle grid:

In the above-mentioned example, you can see that we have a 2D grid containing twenty-five cells. Some of the words we can find on the grid are CAT, MOON, SAILOR, and COIL. In Python code, this grid will be represented by an array of arrays. For the example above, the grid will be [['C', 'S', 'L', 'I', 'M'], ['O', 'I', 'L', 'M', 'O'], ['O', 'L', 'I', 'E', 'O'], ['R', 'T', 'A', 'S', 'N'], ['S', 'I', 'T', 'A', 'C']]. If the word you need to find is COIL, the program should return true in this case. However, if the word to find is COCOON, it should return false.

Solution

The intuition behind this problem’s solution is a backtracking strategy with Depth First Search (DFS) exploration. For each cell on the Boggle grid, we have four paths we can take next. If the chosen path is incorrect, we will backtrack ...