mazeSolverRecursiveBackTrack.py

def solution(maze, n):
    # Type your solution here 
    
    def isGoal(i,j):
        if i == n-1 and j == n-1 and maze[i][j] ==  0:
            return True
        else:
            return False
    
    def isValid(i,j, maze):
        if i >= 0 and i < n and j >= 0 and j < n and maze[i][j] == 0:
            print('isvalid')
            return True
        else:
            print('is invalid')
            return False
    
    def printSolution(maze):
        for i in maze:
            for j in i:
                print(str(j) + " ", end = "")
            print()
    
    def solveMaze(maze):
        solution = [ [0 for j in range(n)] for i in range(n)]
        if solveMazeHelper(maze, 0 , 0, solution) == False:
           return False
        return True
    
    def solveMazeHelper(maze, x,y, sol):
        print('solution', sol)
        if isGoal(x,y):
            print('reached goal')
            sol[x][y] = 1
            return True
        
        if isValid(x,y,maze):
            
            if sol[x][y] == 1: #if already in solution
                return False
            
            sol[x][y] = 1
            
            if solveMazeHelper(maze,x+1,y,sol) == True: #try all directions, if solution/goal state
                return True
            if solveMazeHelper(maze,x,y+1,sol) == True:
                return True
            if solveMazeHelper(maze,x-1,y,sol) == True:
                return True
            if solveMazeHelper(maze,x,y-1,sol) == True:
                return True
            
            sol[x][y] = 0 # back track
            return False
        return False
            
    solveMaze(maze)