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