Word Search in Maze using Depth First Search (with python code and step by step code execution walkthrough)

 

1. Introduction

In this blog, we will explain how to solve the word search problem in a maze using Depth First Search (DFS) algorithm. We will use a 3x3 maze and search for the word 'the' in the maze. The word 'the' is located in the second row of the maze.

2. Algorithm Explanation

The DFS algorithm is used to explore all possible paths in the maze to find the target word. We start from each cell in the maze and recursively explore its neighbors to find the word.

2.1 Steps of the Algorithm

  • Start from each cell in the maze.
  • Check if the current cell matches the current character of the word.
  • Mark the current cell as visited.
  • Recursively explore the neighboring cells (up, down, left, right).
  • Unmark the current cell and backtrack if the word is not found.
  • Return true if the word is found, otherwise return false.

3. Python Code


def dfs(maze, word, i, j, index):
    if index == len(word):
        return True
    if i < 0 or i >= len(maze) or j < 0 or j >= len(maze[0]) or maze[i][j] != word[index]:
        return False

    temp = maze[i][j]
    maze[i][j] = '#'
    found = (dfs(maze, word, i+1, j, index+1) or
             dfs(maze, word, i-1, j, index+1) or
             dfs(maze, word, i, j+1, index+1) or
             dfs(maze, word, i, j-1, index+1))
    maze[i][j] = temp
    return found

def word_search(maze, word):
    for i in range(len(maze)):
        for j in range(len(maze[0])):
            if dfs(maze, word, i, j, 0):
                return True
    return False

maze = [
    ['t', 'a', 'b'],
    ['t', 'h', 'e'],
    ['o', 'f', 'g']
]

word = "the"
print(word_search(maze, word))

4. Example Maze

The example maze is a 3x3 grid with the word 'the' located in the second row:

tab
the
ofg

Step-by-Step Walkthrough 

Initial State

  • Maze: [['t', 'a', 'b'], ['t', 'h', 'e'], ['o', 'f', 'g']]
  • Word: 'the'
  • Starting Point: (0, 0)

Iteration 1: word_search(maze, 'the')

Calls dfs(maze, 'the', 0, 0, 0)

  • Current Cell: (0, 0)
  • Current Character in Maze: 't'
  • Current Character in Word: 't'
  • Index: 0
  • Mark (0, 0) as visited
  • Explores neighbors: (1, 0), (-1, 0), (0, 1), (0, -1)

Iteration 2: dfs(maze, 'the', 1, 0, 1)

Calls dfs(maze, 'the', 1, 0, 1)

  • Current Cell: (1, 0)
  • Current Character in Maze: 't'
  • Current Character in Word: 'h'
  • Index: 1
  • Characters do not match: Backtracks and return False

Iteration 3: dfs(maze, 'the', 0, 1, 1)

Calls dfs(maze, 'the', 0, 1, 1)

  • Current Cell: (0, 1)
  • Current Character in Maze: 'a'
  • Current Character in Word: 'h'
  • Index: 1
  • Characters do not match: Backtracks and return False

Iteration 4: word_search(maze, 'the')

Calls dfs(maze, 'the', 1, 0, 0)

  • Current Cell: (1, 0)
  • Current Character in Maze: 't'
  • Current Character in Word: 't'
  • Index: 0
  • Mark (1, 0) as visited
  • Explores neighbors: (2, 0), (0, 0), (1, 1), (1, -1)

Iteration 5: dfs(maze, 'the', 1, 1, 1)

Calls dfs(maze, 'the', 1, 1, 1)

  • Current Cell: (1, 1)
  • Current Character in Maze: 'h'
  • Current Character in Word: 'h'
  • Index: 1
  • Mark (1, 1) as visited
  • Explores neighbors: (2, 1), (0, 1), (1, 2), (1, 0)

Iteration 6: dfs(maze, 'the', 1, 2, 2)

Calls dfs(maze, 'the', 1, 2, 2)

  • Current Cell: (1, 2)
  • Current Character in Maze: 'e'
  • Current Character in Word: 'e'
  • Index: 2
  • Mark (1, 2) as visited
  • Word found: Return True

Backtracking

After finding the word, we backtrack to unmark the visited cells.

Step 1: Unmark (1, 2)

  • Current Cell: (1, 2)
  • Unmark (1, 2)

Step 2: Unmark (1, 1)

  • Current Cell: (1, 1)
  • Unmark (1, 1)

Step 3: Unmark (1, 0)

  • Current Cell: (1, 0)
  • Unmark (1, 0)

Detailed Function Call Diagram for DFS Execution

Function Call Diagram


word_search(maze, 'the')
  -> dfs(maze, 'the', 0, 0, 0)
       -> (maze[0][0] == 't') == (word[0] == 't') -> True
       -> Explore neighbors: (1, 0), (-1, 0), (0, 1), (0, -1)

    -> dfs(maze, 'the', 1, 0, 1)
         -> (maze[1][0] == 't') != (word[1] == 'h') -> False

    -> dfs(maze, 'the', 0, 1, 1)
         -> (maze[0][1] == 'a') != (word[1] == 'h') -> False

  -> dfs(maze, 'the', 1, 0, 0)
       -> (maze[1][0] == 't') == (word[0] == 't') -> True
       -> Explore neighbors: (2, 0), (0, 0), (1, 1), (1, -1)

    -> dfs(maze, 'the', 1, 1, 1)
         -> (maze[1][1] == 'h') == (word[1] == 'h') -> True
         -> Explore neighbors: (2, 1), (0, 1), (1, 2), (1, 0)

    -> dfs(maze, 'the', 1, 2, 2)
         -> (maze[1][2] == 'e') == (word[2] == 'e') -> True
         -> Word found, return True

Diagram Explanation

  • word_search starts from each cell and calls dfs.
  • dfs(maze, 'the', 0, 0, 0) starts from cell (0, 0) with the first character 't' and succeeds.
  • dfs(maze, 'the', 1, 0, 1) moves to cell (1, 0) with the second character 'h' and fails.
  • dfs(maze, 'the', 0, 1, 1) moves to cell (0, 1) with the second character 'h' and fails.
  • dfs(maze, 'the', 1, 0, 0) starts from cell (1, 0) with the first character 't' and succeeds.
  • dfs(maze, 'the', 1, 1, 1) moves to cell (1, 1) with the second character 'h' and succeeds.
  • dfs(maze, 'the', 1, 2, 2) moves to cell (1, 2) with the third character 'e' and succeeds.
  • The word 'the' is found, and the function returns True.

Why Unmarking is Required in the Algorithm

Unmarking cells in the DFS algorithm is required to ensure that we correctly handle multiple starting points and overlapping paths. Let's break down the reasons for unmarking:

1. Multiple Starting Points

In a word search problem, we start the search from multiple cells in the maze. If we don't unmark cells after each search, previously marked cells would incorrectly block subsequent searches starting from different cells.

2. Overlapping Paths

The DFS algorithm explores all possible paths in the maze to find the word. During the search, it may traverse overlapping paths. Unmarking ensures that these cells are available for exploration in other potential paths.

3. Backtracking

The essence of DFS is to explore all possible paths. When a path does not lead to the desired result (i.e., finding the word), the algorithm backtracks and unmarks the cells to allow other paths to be explored.

Example

Consider the maze:


[['t', 'a', 'b'],
 ['t', 'h', 'e'],
 ['o', 'f', 'g']]

When searching for the word "the", starting from cell (0, 0) and finding that cell (1, 0) does not lead to the word, the algorithm backtracks and unmarks cell (1, 0). This allows subsequent searches starting from different cells, such as (1, 0) and exploring further cells (1, 1) and (1, 2).

Unmarking ensures the correctness and completeness of the search, allowing the algorithm to explore every possible path and handle multiple starting points effectively.

If depth first search is new to you, you can learn about it here - https://parucodes.blogspot.com/2024/12/depth-first-search-dfs-and-breadth.html

Support Our Efforts and Earn Together ðŸš€

Visit https://parucodes.github.io/ today and start your journey to becoming a fast, accurate, and confident touch typist.

If you find our website useful and want to support us, consider joining the exciting world of Bitcoin mining on your mobile phone. Follow this link: Mine PI Bitcoin and use my username prarthanadp as your invitation code. With the referral code prarthanadp, you'll receive a special referral bonus.

Thank you for your support! Let's grow and earn together! 🌟


Comments

Post a Comment

Popular posts from this blog

Recursion examples for Beginners (step by step code execution walkthrough with python code)

  Factorial Explanation and Example Factorial Definition: The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It can be defined recursively as: factorial(0) = 1 (Base Case) factorial(n) = n * factorial(n-1) (Recursive Case) +----------------------------------+ | factorial(n) | | +---------------------------+ | | Base Case: | | | factorial(0) = 1 | | +---------------------------+ | | Recursive Case: | | | factorial(n) = n * | | | factorial(n-1)| | +---------------------------+ +----------------------------------+ Python Code for Factorial def factorial(n): if n == 0: return 1 else: return n * factorial(n - 1) # Example Usage print(factorial(5...
Read more

Handling hierarchical Data using Dictionaries for beginners (with python code)

  Handling Hierarchical Data with Python Dictionaries 1. Introduction to Hierarchical Data Hierarchical data is organized into a tree-like structure with different levels of depth. Each level contains unique objects that are connected to objects in the level above. This type of data is common in various domains, such as organizational structures, file systems, and biological classifications. 2. Example Data We'll create a 5-level hierarchical data structure. The data represents an organizational hierarchy with departments, teams, managers, employees, and tasks. data = { "Department1": { "TeamA": { "Manager1": { "Employee1": { "Task1": "Complete report", "Task2": "Attend meeting" }, "Employee2": { "Task1": "Write...
Read more

Understanding software organization structure for informed career decisions (for freshers)

  Essential Teams in a Software Organization 1. Business Analyst Team Roles and Responsibilities Gathering Requirements: Collecting and documenting software requirements from stakeholders. Analyzing Requirements: Understanding and detailing the requirements to ensure clarity for the development team. Conducting Stakeholder Meetings: Engaging with stakeholders to gather feedback and clarify requirements. Creating Requirement Documents: Producing detailed documentation like Business Requirement Documents (BRD) and Functional Requirement Documents (FRD). Skills Needed Communication Skills: Ability to clearly convey information to stakeholders and team members. Analytical Thinking: Breaking down complex requirements into actionable steps. Documentation Skills: Creating clear and comprehensive requirement documents. Stakeholder Management: Handling various stakeholders' expectations and feedback. Job Titles Business Analyst (BA) Senior Busines...
Read more