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

# 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 []