Find a path in a maze from start to finish

Problem

Given a 2D array which represents a maze, a start point, and an end point, find a path from the start point to the end point if it exists.

Input

• maze: 2D boolean array of size greater than 1 x 1, where False represents a wall (not traversable) and True represents an empty space (traversable)
• start: an object with x, y coordinates
• end: an object with x, y coordinates

Approach

The key to solving this problem is DFS. First look at the start point's adjacent blocks, and for each of those blocks, look at their adjacent blocks, etc. until you reach the coordinates of the end point.

An invalid block would be any block that has a value of False in the maze matrix, or any block with invalid coordinates (i.e. an x-coordinate of -1 means that it is not within the dimensions of the matrix). This will be the base case.

To look at each of the adjacent blocks, there could only be 4 possible choices: up, down, left, and right.

Solution

import collections  
Coordinate = collections.namedtuple("Coordinate", "x y")


def find_paths(maze, start, end):  
    path = []

    def _dfs(curr):
        if curr.x < 0 or curr.x >= len(maze) \
                or curr.y < 0 or curr.y >= len(maze) \
                or maze[curr.y][curr.x] == False:
            return False
        #  This step can possibly lead to the end, so add it to the path
        path.append(curr)

        if curr == end:
            return True

        found = _dfs(Coordinate(x=curr.x-1, y=curr.y)) or \
                _dfs(Coordinate(x=curr.x+1, y=curr.y)) or \
                _dfs(Coordinate(x=curr.x, y=curr.y+1)) or \
                _dfs(Coordinate(x=curr.x, y=curr.y-1))

        if found:
            return True
        else:
            #  Undo the last step since this step does not lead to the end
            del path[-1]
            return False

    if _dfs(start):
        return path

    return []