Building a maze solver

Let's use the A* algorithm to solve a maze. Consider the following figure:

Figure 12: Example of a maze problem

The # symbols indicate obstacles. The symbol o represents the starting point, and x represents the goal. The goal is to find the shortest path from the start to the end point. Let's see how to do it in Python. The following solution is a variant of the solution provided in the simpleai library. Create a new Python file and import the following packages:

import math
from simpleai.search import SearchProblem, astar

Create a class that contains the methods needed to solve the problem:

# Class containing the methods to solve the maze 
class MazeSolver(SearchProblem):

Define the initializer method:

    # Initialize the class
    def __init__(self, board):
        self.board = board
        self.goal = (0, 0)

Extract the initial and final positions:

        for y in range(len(self.board)):
 ...