Maze Solver in Python

Create a file named maze_solver.py and add the following code:

pythonCopy codeclass Maze:
    def __init__(self, grid):
        self.grid = grid
        self.rows = len(grid)
        self.cols = len(grid[0]) if self.rows > 0 else 0
        self.path = []

    def is_valid_move(self, x, y):
        """Check if the move is within the maze boundaries and not a wall."""
        return 0 <= x < self.rows and 0 <= y < self.cols and self.grid[x][y] == 0

    def solve_maze(self, x, y):
        """Solve the maze using DFS."""
        # Check if we reached the exit
        if (x, y) == (self.rows - 1, self.cols - 1):
            self.path.append((x, y))
            return True

        # Check if the current position is valid
        if not self.is_valid_move(x, y):
            return False

        # Mark the cell as part of the path
        self.path.append((x, y))
        self.grid[x][y] = 2  # Mark as visited

        # Explore neighbors (right, down, left, up)
        if (self.solve_maze(x + 1, y) or
                self.solve_maze(x, y + 1) or
                self.solve_maze(x - 1, y) or
                self.solve_maze(x, y - 1)):
            return True

        # Unmark the cell if not part of the solution
        self.path.pop()
        self.grid[x][y] = 0  # Unmark as visited
        return False

    def print_solution(self):
        """Print the path found."""
        if self.path:
            print("Path to the exit:")
            for step in self.path:
                print(step)
        else:
            print("No path found.")

def main():
    # Define the maze (0 = path, 1 = wall)
    maze_grid = [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0],
        [0, 1, 1, 1, 0]
    ]

    maze = Maze(maze_grid)

    # Solve the maze starting from the top-left corner (0, 0)
    if maze.solve_maze(0, 0):
        maze.print_solution()
    else:
        print("No path from the start to the exit.")

if __name__ == "__main__":
    main()

Step 2: Running the Maze Solver

1. Open your terminal (or command prompt).
2. Navigate to the directory where you saved maze_solver.py.
3. Run the script using the command:bashCopy codepython maze_solver.py

How It Works

• Maze Representation: The maze is represented as a 2D list (grid), where 0 represents open paths and 1 represents walls.
• DFS Algorithm: The solve_maze method uses Depth-First Search to explore the maze:
  • It checks if the current position is valid.
  • If it reaches the exit (bottom-right corner), it returns True.
  • It marks the cell as visited by changing it to 2.
  • It recursively explores neighboring cells.
  • If a cell doesn’t lead to a solution, it backtracks by unmarking the cell.
• Path Tracking: The path to the exit is tracked and printed if found.

Example Maze

The maze defined in the code looks like this:

Copy code0 1 0 0 0
0 1 0 1 0
0 0 0 1 0
1 1 0 0 0
0 1 1 1 0