Python:

# Classes for working with mazes

# This function takes a string as input, and returns a list of the ints in the

# string. This is used by the Maze constructor.

def parse_line(line):

line_contents = line.split()

i = 0

while i

line_contents[i] = int(line_contents[i])

i = i + 1

return line_contents

# Represents a Maze, with any number of squares.

class Maze:

# Creates a new maze:

def __init__(self, file_name):

file = open(file_name, "r")

maze_size = parse_line(file.readline())

self.__squares = []

for x in range(0, maze_size[0]):

self.__squares.append([0] * maze_size[1])

x = 0

while x

y = 0

while y

square = MazeSquare(x, y)

self.__squares[x][y] = square

y = y + 1

x = x + 1

start_location = parse_line(file.readline())

self.__start = self.__squares[start_location[0]][start_location[1]]

finish_location = parse_line(file.readline())

self.__finish = self.__squares[finish_location[0]][finish_location[1]]

for line in file:

legal_move = parse_line(line)

self.__squares[legal_move[0]][legal_move[1]].add_move(

self.__squares[legal_move[2]][legal_move[3]])

# Returns the start square of this maze:

def get_start_square(self):

return self.__start

# Returns True if the square is the finish square, and False otherwise:

def is_finish_square(self, square):

if square == self.__finish:

return True

else:

return False

# Represents a single square in a maze.

class MazeSquare:

def __init__(self, x, y):

self.__moves = []

self.__x = x

self.__y = y

def add_move(self, neighbor):

self.__moves.append(neighbor)

def get_legal_moves(self):

return self.__moves

def get_location(self):

return (self.__x, self.__y)

solvable_maze.txt

3 3

0 0

2 2

0 0 0 1

0 1 0 2

0 1 1 1

0 2 1 2

1 1 2 1

2 1 2 2

2 1 2 0

2 0 1 0

unsolvable_maze.txt

3 3

0 0

2 2

0 0 0 1

0 1 0 2

0 2 1 2

1 2 1 1

1 1 1 0

1 1 2 1

1 0 2 0

Q2. Write a program that uses the Stack implementation given to you in Stack.py to check if there is a solution to a maze or not. If there is a solution, your program shows the message Goal is reached, if there is no solution your program shows the message Goal is Unreachable A simple maze implementation is given to you in maze.py Hint: You don't need to change anything in file maze.py To solve a maze using the Stack, use the following algorithm 1. Add the start square to the stack. 2. Repeat the following as long as the stack is not empty Pop a square off the stack (the current square) If the current square is the finish square, the solution has been found Otherwise, get the list of squares which can be moved to from the current square, and add them to the stack Description of maze.py .The maze.py file has two classes: Maze and MazeSquare. The Maze class represents the entire maze and the MazeSquare class represents a single square in the Maze You can create a new instance of Maze class by calling the constructor: my-maze Maze(filename), where filename is the name of a text file containing a maze .You can get the start square of the maze by calling my_maze.get start square). This method returns an object of type MazeSquare To check if a square is the finish square call my maze.is_ finish square(square), where square is of type MazeSquare The get legal moves) is a method in the MazeSquare class. This method returns a list of objects of type MazeSquare that can be moved to. Let's say if square is an identifier that is bound to an object of type MazeSquare then get legal moves) can be called in the following manner list of legal_moves square.get legal moves)