This is another coding interview question. Find a path through a labyrinth. Let's assume the labyrinth is given as a string of the following form:

maze = """ XXXXXXXXXXX X X X XXXXX X X XX X X X XX X XXXXXXXXXXX """

The first thing to do is to convert this string into a more suitable data structure. A boolean matrix springs to mind, where `true` indicates an empty cell and `false` a stone. It is a one-liner in Python to convert the string given in `maze` into the boolean matrix:

maze = [[cell!='X' for cell in row] for row in maze.split('\n')[1:]]

The function to test for a path from a starting point `start` given as tuple `(row,col)` to an end point `end` can then be implemented as follows:

def find(maze,start,end): stack = [start] while stack: i,j = stack.pop() if not maze[i][j]: continue if (i,j) == end: return True maze[i][j] = False if maze[i][j+1]: stack.append((i,j+1)) if maze[i][j-1]: stack.append((i,j-1)) if maze[i+1][j]: stack.append((i+1,j)) if maze[i-1][j]: stack.append((i-1,j)) return False

Instead of a recursive solution we use a stack to explore all possible paths with backtracking. We initialize the stack with the starting point and then loop as long as there are points on the stack or the end point has been found. In each iteration we take the top point from the stack (`i,j = stack.pop()`) and test if the corresponding cell of the maze is empty. If not we jump to the beginning of the loop. If the cell is empty we mark it as visited (`maze[i][j] = False`) and leave the loop if it is the end point. If we have not reached the end point we push the coordinates of all neighboring empty cells on the stack and keep iterating.

Let's give it a go:

start = (1,1) end = (4,9) print find(maze, start, end)

True

One last thing. The code to test for empty neighboring cells is simple and clear but repetitive. Another solution is to replace those four lines by a loop. It isn't much shorter (three instead of four lines) and the code becomes more complex though:

def find(maze,start,end): stack = [start] while stack: i,j = stack.pop() if (i,j) == end: return True maze[i][j] = False if (i,j) == end: return True for io,jo in [(0,+1),(0,-1),(+1,0),(-1,0)]: ni,nj = i+io,j+jo if maze[ni][nj]: stack.append((ni,nj)) return False