A class to solve a matrix maze. A 0 is wall, and 1 is path. Starting and finishing node is given.

maze_solver.py

class Maze:
    def __init__(self, matrix, start, finish):
        self.maze = matrix
        self.start = start
        self.finish = finish

    def UP(self, i, j):
        try:
            return (self.maze[i-1][j], (i-1, j))
        except:
            return (None, None)

    def DOWN(self, i, j):
        try:
            return (self.maze[i+1][j], (i+1, j))
        except:
            return (None, None)

    def LEFT(self, i, j):
        try:
            return (self.maze[i][j-1], (i, j-1))
        except:
            return (None, None)

    def RIGHT(self, i, j):
        try:
            return (self.maze[i][j+1], (i, j+1))
        except:
            return (None, None)

    #Returns the list of possible paths in case of junction
    def isJunction(self, i, j):
        jnc = []
        if self.UP(i, j)[0]:
            jnc.append(self.UP(i, j)[1])
        if self.DOWN(i, j)[0]:
            jnc.append(self.DOWN(i, j)[1])
        if self.LEFT(i, j)[0]:
            jnc.append(self.LEFT(i, j)[1])
        if self.RIGHT(i, j)[0]:
            jnc.append(self.RIGHT(i, j)[1])

        if len(jnc) > 2:
            return jnc
        else:
            return []


    def getSolution(self):

        visited = [self.start]  #store the visited nodes
        jncQueue = []      #if junction found, store the possible paths
        solution = [self.start] #solution path #number of nodes added after each junction

        i, j = self.start       #starting node
    
        #run this loop until finishing node is visited
        while self.finish not in visited:
            up = self.UP(i, j)
            down = self.DOWN(i, j)
            left = self.LEFT(i, j)
            right = self.RIGHT(i, j)
            
            if up[0] and up[1] not in visited:
                i -= 1
            elif down[0] and down[1] not in visited:
                i += 1
            elif left[0] and left[1] not in visited:
                j -= 1
            elif right[0] and right[1] not in visited:
                j += 1
            elif jncQueue:
                i, j = jncQueue.pop(0) #back to last junction
            else:
                return [] #NO SOLUTION

            if (i, j) not in visited:
                visited.append((i,j))
                solution.append((i,j))

            if (i, j) in jncQueue and (i, j) in visited:
                jncQueue.remove((i, j)) #Removes the node if it is visited

            is_jnc_i_j = self.isJunction(i, j)
            if is_jnc_i_j:
                for item in is_jnc_i_j:
                    if item not in visited:
                        jncQueue.append(item)

        return solution


#DRIVER CODE
matrix = [[0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
          [0, 1, 1, 1, 1, 1, 1, 1, 1, 0],
          [0, 1, 0, 0, 0, 1, 0, 0, 1, 0],
          [0, 1, 0, 0, 0, 1, 1, 0, 1, 0],
          [0, 1, 0, 0, 0, 1, 0, 0, 1, 0],
          [0, 1, 1, 1, 0, 0, 0, 0, 1, 0],
          [0, 1, 0, 1, 0, 1, 1, 1, 1, 0],
          [0, 1, 1, 1, 0, 1, 1, 1, 0, 0],
          [0, 0, 0, 0, 0, 1, 0, 1, 1, 1],
          [0, 0, 0, 0, 0, 1, 1, 0, 0, 0]]

start = (0, 3)
finish = (9, 6)

myMaze = Maze(matrix, start, finish)

print(myMaze.getSolution())