Let's Solve the Maze using Learning Algorithm | Depth first search (DFS) &Breadth first search (BFS) 

What is Depth first search (DFS)?

Depth-first search (DFS) is an algorithm for searching a graph or tree data structure. The algorithm starts at the root (top) node of a tree and goes as far as it can down a given branch (path), then backtracks until it finds an unexplored path, and then explores it. The algorithm does this until the entire graph has been explored.

The process involves selecting a path in the maze according to a predetermined rule and following it until either a dead end is reached, or the maze's endpoint is found. If the chosen path proves unsuccessful, backtracking occurs to a previous junction to explore alternative routes.

What is Breadth first search (BFS)?

It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.

In the context of solving a maze, the process involves exploring all possible paths from the starting point layer by layer. According to a predetermined rule, each path is followed one step at a time, and all adjacent nodes are explored before moving deeper. If the endpoint of the maze is found, the search concludes. If a path leads to a dead end, the algorithm continues with the next unexplored path from the closest junction to the start. This ensures that all potential routes are systematically explored.

Python code 

Node class:

  • State: Represents the current state of the node
  • Parent: Reference to the parent node, used to trace the path back to the initial state.
  • Action: The action taken to reach this node from the parent node, used to reconstruct the sequence of actions leading to the current state.
class Node():
            def __init__(self, state, parent, action):
                self.state = state
                self.parent = parent
                self.action = action

StackFrontier/DFS class:

Implements a stack-based frontier for search algorithms, using a Last-In-First-Out (LIFO) strategy.

  • __init__(): Initializes an empty stack.
  • add(node): Adds a node to the frontier.
  • contains_state(state): Checks if a given state is already in the frontier.
  • empty(): Checks if the frontier is empty.
  • remove(): Removes and returns the last node added to the frontier. Raises an exception if the frontier is empty.
class StackFrontier():
            def __init__(self):
                self.frontier = []
        
            def add(self, node):
                self.frontier.append(node)
        
            def contains_state(self, state):
                return any(node.state == state for node in self.frontier)
        
            def empty(self):
                return len(self.frontier) == 0
        
            def remove(self):
                if self.empty():
                    raise Exception("empty frontier")
                else:
                    node = self.frontier[-1]
                    self.frontier = self.frontier[:-1]
                    return node

QueueFrontier/BFS class:

Extends StackFrontier to implement a queue-based frontier for search algorithms, using a First-In-First-Out (FIFO) strategy.

  • Inherits all methods from StackFrontier.
  • remove(): Removes and returns the first node added to the frontier. Raises an exception if the frontier is empty. Overrides the remove method of StackFrontier.
class QueueFrontier(StackFrontier):
        
            def remove(self):
                if self.empty():
                    raise Exception("empty frontier")
                else:
                    node = self.frontier[0]
                    self.frontier = self.frontier[1:]
                    return node

The Maze class provides methods to validate, construct, and visualise a maze. It uses BFS/DFS to find and print the shortest path from the start to the goal, indicating the path taken if a solution exists.

  • Initialization (__init__):
    • Validates the maze to ensure it contains exactly one start point ("A") and one goal ("B").
    • Determines the height and width of the maze.
    • Constructs the maze grid, marking walls and identifying the start and goal positions.
  • Printing (print):
    • Prints a visual representation of the maze.
    • If a solution is found, it marks the solution path with asterisks (*).
  • Neighbors (neighbors):
    • Returns the valid neighboring cells (up, down, left, right) of a given cell that are not walls.
  • Solve (solve):
    • Implements a breadth-first search (BFS) to find the shortest path from the start to the goal.
    • Initializes the search with the start position.
    • Explores nodes until it finds the goal or exhausts all possibilities.
    • Constructs the solution path if the goal is reached, storing the sequence of actions and cells.
class Maze():
        
            def __init__(self, contents):
        
                # Validate start and goal
                if contents.count("A") != 1:
                    raise Exception("maze must have exactly one start point")
                if contents.count("B") != 1:
                    raise Exception("maze must have exactly one goal")
        
                # Determine height and width of maze
                contents = contents.splitlines()
                self.height = len(contents)
                self.width = max(len(line) for line in contents)
        
                # Keep track of walls
                self.walls = []
                for i in range(self.height):
                    row = []
                    for j in range(self.width):
                        try:
                            if contents[i][j] == "A":
                                self.start = (i, j)
                                row.append(False)
                            elif contents[i][j] == "B":
                                self.goal = (i, j)
                                row.append(False)
                            elif contents[i][j] == " ":
                                row.append(False)
                            else:
                                row.append(True)
                        except IndexError:
                            row.append(False)
                    self.walls.append(row)
        
                self.solution = None
        
        
            def print(self):
                solution = self.solution[1] if self.solution is not None else None
                print()
                for i, row in enumerate(self.walls):
                    for j, col in enumerate(row):
                        if col:
                            print("█", end="")
                        elif (i, j) == self.start:
                            print("A", end="")
                        elif (i, j) == self.goal:
                            print("B", end="")
                        elif solution is not None and (i, j) in solution:
                            print("*", end="")
                        else:
                            print(" ", end="")
                    print()
                print()
        
        
            def neighbors(self, state):
                row, col = state
                candidates = [
                    ("up", (row - 1, col)),
                    ("down", (row + 1, col)),
                    ("left", (row, col - 1)),
                    ("right", (row, col + 1))
                ]
        
                result = []
                for action, (r, c) in candidates:
                    if 0 <= r < self.height and 0 <= c < self.width and not self.walls[r][c]:
                        result.append((action, (r, c)))
                return result
        
        
            def solve(self):
                """Finds a solution to maze, if one exists."""
        
                # Keep track of number of states explored
                self.num_explored = 0
        
                # Initialize frontier to just the starting position
                start = Node(state=self.start, parent=None, action=None)
                frontier =QueueFrontier()
                frontier.add(start)
        
                # Initialize an empty explored set
                self.explored = set()
        
                # Keep looping until solution found
                while True:
        
                    # If nothing left in frontier, then no path
                    if frontier.empty():
                        raise Exception("no solution")
        
                    # Choose a node from the frontier
                    node = frontier.remove()
                    self.num_explored += 1
        
                    # If node is the goal, then we have a solution
                    if node.state == self.goal:
                        actions = []
                        cells = []
                        while node.parent is not None:
                            actions.append(node.action)
                            cells.append(node.state)
                            node = node.parent
                        actions.reverse()
                        cells.reverse()
                        self.solution = (actions, cells)
                        return
        
                    # Mark node as explored
                    self.explored.add(node.state)
        
                    # Add neighbors to frontier
                    for action, state in self.neighbors(node.state):
                        if not frontier.contains_state(state) and state not in self.explored:
                            child = Node(state=state, parent=node, action=action)
                            frontier.add(child)

Try it out 

create a maze.txt

###                 #########
        #   ###################   # #
        # ####                # # # #
        # ################### # # # #
        #                     # # # #
        ##################### # # # #
        #   ##                # # # #
        # # ## ### ## ######### # # #
        # #    #   ##B#         # # #
        # # ## ################ # # #
        ### ##             #### # # #
        ### ############## ## # # # #
        ###             ##    # # # #
        ###### ######## ####### # # #
        ###### ####             #   #
        A      ######################

Run the code below to see how the algorithm solves the maze:

with open('maze.txt') as f:
            contents = f.read()
        m = Maze(contents)
        m.print()
        m.solve()
        print("States Explored:", m.num_explored)
        m.print()

In this output, the asterisks (*) indicate the path taken from the start to the goal.

To use StackFrontier i.e DFS just replace the class QueueFrontier you can find this in the Maze class

Conclusion 

This example demonstrates how you can use Python to solve a maze using the breadth-first search algorithm. The Mazeclass is versatile and can handle different maze configurations, making it a powerful tool for pathfinding problems. Try modifying the maze and see how the algorithm performs with different layouts!