[The description of the problem and the skeleton code is given below. You will have to insert your own code but maintain the code structure. One small change that you will need to do is use print() instead of print in the code.In addition to BFS, you will need to implement A* search for this problem. ]

To apply this algorithm to a maze, think of grid locations as vertices. The "children" of a grid location are the open cells adjacent to it in the four cardinal directions.

A Maze class and an Agent class have been started for you below. Once you complete the indicated methods, you will be able to watch the agent navigate the maze. Adjust the height of your console window to match the maze height, so that each display appears in the same place.

Algorithm notes:

• You will need to keep track of the sequence of moves by which you discovered each location. The pseudocode above doesn't address this, so the way you do it is up to you.
• You will also need to decide how you want to represent moves.

Python notes:

use python

Breadth-first search in a maze Command Output X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X XXX XXX X X X X XXX X X X X X X X X X X X X X XXX xxxxxx XXX X X X XXX X x XXX X X X X X X X X X X X X X X X x XXX X X X X X X X X X X X X X X X X X X X X X xx x x x X X X X X X X X X XXX X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X xxxx The goal of this assignment is to find your way out of a maze using breadth-first search. Here is a basic algorithm for BFS in an unweighted graph: bfs(start vertex,_goal vertex) make frontier an empty queue enqueue start onto frontier until frontier is empty dequeue parent off frontier for each undiscovered child of parent enqueue child onto frontier stop if child is the goal import time class Maze (object): "A pathfinding problem. HHH def __init__(self, grid, location): """Instances differ by their current agent locations." self.grid grid self.location = location = def display (self): """Print the maze, marking the current agent location." for r in range (len(self.grid)): for c in range(len(self.grid[r])): if (r, c) == self.location: print '*', else: print self.grid[r][c], print print def moves(self): " "Return a list of possible moves given the current agent location.' # YOU FILL THIS IN def neighbor(self, move): "" "Return another Maze instance with a move made. # YOU FILL THIS IN # YOU FILL THIS IN class Agent (object): "*"Knows how to find the exit to a maze with BFS. def bfs (self, maze, goal): "Return an ordered list of moves to get the maze to match the goal. # YOU FILL THIS IN def main(): ***"Create a maze, solve it with BFs, and console-animate.' grid = "X "X ["XXXXXXXXXXXXX XXXXX", x x X", "X XXXXX XXXX XXX XXX", X X XX", "X X XXX XXXXXX X X X", "X X X X XX", "X XXX XXXXXX XXXXX X", "X XXX XXX X", "X XXX XXXXX", "XXXXX XXXXXX X", "X XXX X X X X X", "XXX XXX X X XXXX "X xx XX X X X", "XXXXX XXXX X XXX", "X X XXX X", "X XXXXX X XXXX XXX X", "X X x xx "X X XXXXXX X XXXXX X", "XX "XXXXXXXXXXXXXXXXXX X"] X", X", X", maze = Maze (grid, (1,1)) maze.display) = agent goal path Agent) Maze (grid, (19,18)) agent.bfs (maze, goal) = while path: move - path.pop() maze = maze.neighbor(move) time. sleep(0.25) maze.display) if == _main__': name main()