Earlier this year, when I was looking for work, I got the same recursive maze problem three interviews in a row. Recursion is cute and clever, but you generally want to use iterative solutions in production.

Usually, you get a string representation of the maze, something like:

ms = '''
S####
....#
#.###
....G
##..#
...##
#..##
'''

So then you need to parse that into a list of lists, which isn’t difficult:

def maze_string_to_list_of_lists(maze: str) -> []:
    rows = maze.split()
    new_maze = []
    for row in rows:
        new_row = [i for i in row]
        new_maze.append(new_row)
    return new_maze

Next, I like to write a function to return cells orthogonal to some cell location. This originally considered cells north, south, east, and west of a location, but then I limited it to just south and east, because this is recursive and we have to worry about the stack size in Python. (Because recursion is as stupid as it is clever.)

def orthogonals(row: int, col: int, row_limit: int, col_limit: int) -> []:
    result = []
    # check input
    if row < 0 or row >= row_limit:
        return result
    if col < 0 or col >= col_limit:
        return result
    # compute output
    s = [row+1, col]
    e = [row, col+1]
    # check computed output
    if s[0] < row_limit:
        result.append(s)
    if e[1] < col_limit:
        result.append(e)
    return result

Finally, the meat and potatoes. Yeah, so SOLN is a global variable that’s laying around, which is bad. You know what else is bad? Recursive maze solvers.

SOLN = []

def find_path(row: int, col: int, maze: list) -> bool:
    if maze[row][col] == 'G':
        SOLN.append([row, col])
        return True
    if maze[row][col] == '#':
        return False
    SOLN.append([row, col])
    orthos = orthogonals(row, col, len(maze), len(maze[0]))
    for ortho in orthos:
        if ortho in SOLN:
            pass
        if find_path(ortho[0], ortho[1], maze):
            return True
    SOLN.pop()
    return False

References:

• (Recursion: Solving a Maze)[https://www.cs.bu.edu/teaching/alg/maze/]
• (Backtracking: Rat in a Maze)[http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/]