Testing for a path through a maze

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