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/]