Codex-assisted ASCII maze solver

maze.py

class Square:
    """
    Represents a square in the maze.
    """

    WALL = 0
    OPEN = 1
    START = 2
    EXIT = 3

    def __init__(self, type):
        """
        Creates a new square of the given type.
        """
        self.type = type

    def get_type(self):
        """
        Returns the type of the square.
        """
        return self.type

    def is_wall(self):
        """
        Returns true if the square is a wall.
        """
        return self.type == Square.WALL

    def is_open(self):
        """
        Returns true if the square is open.
        """
        return self.type == Square.OPEN

    def is_start(self):
        """
        Returns true if the square is a start square.
        """
        return self.type == Square.START

    def is_exit(self):
        """
        Returns true if the square is an exit square.
        """
        return self.type == Square.EXIT

    def __str__(self):
        """
        Returns a string representation of the square.
        """
        if self.is_wall():
            return '#'
        elif self.is_start():
            return 'S'
        elif self.is_exit():
            return 'E'
        elif self.is_open():
            return ' '
        else:
            return '?'

class Maze:
    """
    Represents a maze.
    """

    def __init__(self, width, height):
        """
        Creates a new maze with the given width and height.
        """
        self.width = width
        self.height = height
        self.grid = []
        for y in range(self.height):
            row = []
            for x in range(self.width):
                row.append(Square.OPEN)
            self.grid.append(row)

    def get_width(self):
        """
        Returns the width of the maze.
        """
        return self.width

    def get_height(self):
        """
        Returns the height of the maze.
        """
        return self.height

    def get_square(self, x, y):
        """
        Returns the type of square at the given location.
        """
        return self.grid[y][x]

    def set_square(self, x, y, square):
        """
        Sets the type of square at the given location.
        """
        self.grid[y][x] = square

    def get_start_square(self):
        """
        Returns the location of the start square.
        """
        for y in range(self.height):
            for x in range(self.width):
                if self.get_square(x, y) == Square.START:
                    return (x, y)
        raise Exception('Maze has no start.')

    def get_exit_square(self):
        """
        Returns the location of the exit square.
        """
        for y in range(self.height):
            for x in range(self.width):
                if self.get_square(x, y) == Square.EXIT:
                    return (x, y)
        raise Exception('Maze has no exit.')

    def is_wall(self, x, y):
        """
        Returns true if there is a wall at the given location.
        """
        return self.get_square(x, y) == Square.WALL

    def is_open(self, x, y):
        """
        Returns true if there is no wall at the given location.
        """
        return self.get_square(x, y) == Square.OPEN

    def is_start(self, x, y):
        """
        Returns true if there is a start square at the given location.
        """
        return self.get_square(x, y) == Square.START

    def is_exit(self, x, y):
        """
        Returns true if there is an exit square at the given location.
        """
        return self.get_square(x, y) == Square.EXIT

    def __str__(self):
        """
        Returns a string representation of the maze.
        """
        s = ''
        for y in range(self.height):
            for x in range(self.width):
                if self.is_wall(x, y):
                    s += '#'
                elif self.is_start(x, y):
                    s += 'S'
                elif self.is_exit(x, y):
                    s += 'E'
                elif self.is_open(x, y):
                    s += ' '
            s += '\n'
        return s

class Solver:
    """
    A fast maze solver using a breadth first search algorithm.
    """

    def __init__(self, maze):
        """
        Creates a new maze solver that solves the given maze.
        """
        self.maze = maze
        self.start_square = self.get_start_square()
        self.exit_square = self.get_exit_square()
        self.queue = [self.start_square]
        self.visited = []

    def get_start_square(self):
        """
        Returns the square that the solver will start at.
        """
        for y in range(self.maze.get_height()):
            for x in range(self.maze.get_width()):
                if self.maze.get_square(x, y) == Square.START:
                    return (x, y)
        raise Exception('Maze has no start.')

    def get_exit_square(self):
        """
        Returns the square that the solver will finish at.
        """
        for y in range(self.maze.get_height()):
            for x in range(self.maze.get_width()):
                if self.maze.get_square(x, y) == Square.EXIT:
                    return (x, y)
        raise Exception('Maze has no exit.')


    def get_neighbors(self, square):
        """
        Returns a list of the neighbors of the given square.
        """
        x, y = square
        neighbors = []
        if x > 0:
            neighbors.append((x - 1, y))
        if x < self.maze.get_width() - 1:
            neighbors.append((x + 1, y))
        if y > 0:
            neighbors.append((x, y - 1))
        if y < self.maze.get_height() - 1:
            neighbors.append((x, y + 1))
        return neighbors

    def solve(self):
        """
        Solves the maze. Returns True if the maze is solvable and false
        otherwise.
        """
        while len(self.queue) > 0:
            square = self.queue.pop(0)
            self.visited.append(square)
            if square == self.exit_square:
                return True
            for neighbor in self.get_neighbors(square):
                if neighbor not in self.visited and not self.maze.is_wall(neighbor):
                    self.queue.append(neighbor)
        return False

    def __str__(self):
        """
        Returns a string representation of the maze including the path taken to solve the maze.
        """
        s = ''
        for y in range(self.maze.get_height()):
            for x in range(self.maze.get_width()):
                if self.maze.is_wall(x, y):
                    s += '#'
                elif self.maze.is_start(x, y):
                    s += 'S'
                elif self.maze.is_exit(x, y):
                    s += 'E'
                elif (x, y) in self.visited:
                    s += '.'
                elif self.maze.is_open(x, y):
                    s += ' '
            s += '\n'
        return s

if __name__ == '__main__':
    maze = Maze(5, 5)
    maze.set_square(0, 0, Square.WALL)
    maze.set_square(1, 0, Square.WALL)
    maze.set_square(2, 0, Square.WALL)
    maze.set_square(3, 0, Square.WALL)
    maze.set_square(4, 0, Square.WALL)
    maze.set_square(4, 1, Square.WALL)
    maze.set_square(4, 2, Square.WALL)
    maze.set_square(4, 3, Square.WALL)
    maze.set_square(4, 4, Square.WALL)
    maze.set_square(3, 4, Square.WALL)
    maze.set_square(2, 4, Square.WALL)
    maze.set_square(1, 4, Square.WALL)
    maze.set_square(0, 4, Square.WALL)
    maze.set_square(0, 3, Square.WALL)
    maze.set_square(0, 2, Square.WALL)
    maze.set_square(0, 1, Square.WALL)
    maze.set_square(1, 1, Square.START)
    maze.set_square(2, 2, Square.EXIT)
    print(maze)
    solver = Solver(maze)
    if solver.solve():
        print(solver)
    else:
        print('Maze has no solution.')