# Leetcode 79 – Boggle Game / Word Search

The link above is to the leetcode question. This problem set can be solved using backtracking and depth first search.

The first thing to do when trying to understand these leetcode problems is to actually understand the problem and understand what it is asking you to do. So in this question, you are being asked to find out if a word is found on the game board. However, there are some restrictions.

1. The word must be constructed with sequentially adjacent cells
3. You cannot use the same letter cell twice

So when we first think about this, we can think about the rule set. The third rule is a pretty big giveaway that we want to use a set. The set data structure allows you to only hold unique items.

The first and second rule first makes me think that we are going to be using back tracking. Why? Because it is a situation where we can think of the solution as using a state space tree. We can also apply a bounding function which would restrict the certain “nodes” that we can search for. this would be the adjacent cells. Some pseudo code could look like this:

``````x + 1, y
x - 1, y
x, y + 1
x, y - y``````

These would be our four conditions for the different directions. We would also need to check and ensure that we are not going out of bounds of the game board.

``````def word_found_in_board(board: list[list[str]], word: str) -> bool:
rows = len(board)
columns = len(board[0])
path = set()

def dfs(row: str, column: str, index: int):
if index == len(word):
return True
if row < 0 or column < 0 or row >= rows or column >= columns or word[index] != board[row][column] or (row, column) in path:
return False