maze_solver.py

class MazeSolver:
    def __init__(self, maze):
        self.maze = maze
        self.rows = len(maze)
        self.cols = len(maze[0])
        self.start = self.find_start()
        self.position = self.start
        self.visited = set([self.start])
        self.path = [self.start]

    def find_start(self):
        for i in range(self.rows):
            for j in range(self.cols):
                if self.maze[i][j] == 'S':
                    return (i, j)
        return None

    def is_valid_move(self, position):
        x, y = position
        return 0 <= x < self.rows and 0 <= y < self.cols and self.maze[x][y] != 1

    def get_neighbors(self, position):
        x, y = position
        neighbors = []
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  # Up, Down, Left, Right
            new_pos = (x + dx, y + dy)
            if self.is_valid_move(new_pos):
                neighbors.append(new_pos)
        return neighbors

    def solve(self):
        while True:
            if self.maze[self.position[0]][self.position[1]] == 'E':
                return True  # Exit found

            neighbors = self.get_neighbors(self.position)
            unvisited_neighbors = [n for n in neighbors if n not in self.visited]

            if not unvisited_neighbors:
                # Dead end or loop, backtrack
                if not self.path:
                    return False  # No path to exit
                self.position = self.path.pop()
                continue

            # Choose the next position (right-hand wall-following)
            next_position = min(unvisited_neighbors, key=lambda n: (n[1], n[0]))
            self.visited.add(next_position)
            self.path.append(next_position)
            self.position = next_position