@rkenmi - Find a path in a maze from start to finish

Find a path in a maze from start to finish

Find a path in a maze from start to finish

Back to Top

Updated on February 10, 2019



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.


  • 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


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.


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

        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
            #  Undo the last step since this step does not lead to the end
            del path[-1]
            return False

    if _dfs(start):
        return path

    return []

Article Tags:
unlistedundirected graphconnected componentsmazesgraph traversaldfs