# 2D Maze solver using recursion in Python

A company I interviewed for sent me a coding problem to solve. The problem was to find a solution to a maze, not necessarily the shortest one. The input would be like so:

###_###
#_____#
#_##_##
#_##__#
#_#####


The output would be:

###a###
#dcb__#
#e##_##
#f##__#
#g#####


Walls are represented by '#' and empty space represented by '_'. There can only be a single entrance and a single exit. The entrance will always be in the first row and the exit will always be in the last row. The path should be outlined by the alphabet. If the path requires more than 26 steps, then start over from 'a'.

My solution is like so:

1. Mark entrance as '+' and exit as '-'
2. Call solve() for starting point.
3. Loop neighbors that have empty space to move to and haven't been visited, using a generator.
4. Add neighbor to a list 'paths' that contain the points visited and call solve() for the latest point.
5. If the current point does not have any neighbors to move to, then we've reached a dead-end. So backtrack by popping that point from the 'paths' list, mark it as '!' in the maze and call solve() on the previous point.
6. The function completes when '-' is reached.

Here is the code for it.

class MazeRunner:

def __init__(self, file_path):
self.Point = collections.namedtuple('Point', 'row col')
self.char_wheel = ord('a')
self.paths = []

with open(file_path,'r') as f:
maze = [list(line.rstrip()) for line in f.readlines()]
return maze

def show_maze(self):
for point in self.paths:
self.maze[point.row][point.col] = chr(self.char_wheel)
self.char_wheel += 1

if self.char_wheel > ord('z'):
self.char_wheel = ord('a')

for row in self.maze:
print(row)

def mark_startstop(self):
#Mark starting point with '+'
col_ = self.maze.index('_')
self.maze[col_] = '+'

#Mark stopping point with '-'
col_ = self.maze[-1].index('_')
self.maze[-1][col_] = '-'

yield self.Point(current.row-1, current.col)
yield self.Point(current.row+1, current.col)
yield self.Point(current.row, current.col-1)
yield self.Point(current.row, current.col+1)

def neighbors(self, current):
if pos.row in range(0,len(self.maze)) and pos.col in range(0,len(self.maze)):
if self.maze[pos.row][pos.col] in ['_','-']:
yield pos

def solve(self, current):

print('\nPathing --> ',self.paths)
print('Attempting solve('+str(current)+')\n')

#Base cases
if len(self.paths) < 1:
print('Unsuccessful')
return False

elif self.maze[current.row][current.col] == '-':
print('Maze completed!')
return True

#Recursive case
else:
for point in self.neighbors(current):
print('\tChecking out '+str(point)+' - neighbor of '+str(current))
if  self.maze[point.row][point.col] in ['_','-'] and point not in self.paths:
self.paths.append(point)
return self.solve(self.paths[-1])
else:
print('\tSkipping '+str(point))

self.maze[current.row][current.col] = '!'
temp = self.paths.pop()
return self.solve(self.paths[-1])

def find_path(self):

self.mark_startstop()
start_col = self.maze.index('+')
start_row = 0
self.paths.append(self.Point(start_row, start_col))
self.solve(self.paths[-1])

def main():

parser = ArgumentParser('Maze Runner', description="This program finds solution to mazes given as input")
parser.add_argument('--path', default='maze.txt', help='Path of the file containing the maze')

args = parser.parse_args()

path = args.path
solver = MazeRunner(path)

solver.show_maze()

solver.find_path()
solver.show_maze()


How would you make it better in terms of time/space complexity and readability?

• Have you submitted your solution yet? What feedback did you get? – 200_success Jul 10 '18 at 4:45
• @200_success Yes, I had already submitted my code before posting here. There wasn't much of a feedback from the interviewer but there were follow-up questions about the choices I made such as my use of recursion, generators and time-complexity of the program. – Apoorva Vinod Jul 10 '18 at 23:01

Some initial impressions that I'd note if I was an interviewer:

1. if len(self.paths) < 1 is better written as if len(self.paths) == 0 or if not self.paths
2. In self.neighbors you perform a check to see if an adjacent node is outside the maze. Try moving this logic into self.adjacent
3. Instead of solving recursively, which will fail for mazes longer than 1000 steps, instead use a while self.paths or similar
4. If you want to improve speed slightly (at the cost of space), consider pre-allocating self.paths, by making it large and filled with None. Then you can have a pointer to the current index and manipulate in the same way. However this leads to its own issues
5. For further improvements, consider using BFS instead of your current DFS, and implementing a bidirectional search. This should in theory make the search up to twice as fast. However, there's nothing strictly wrong with what you have
6. Consider first parsing your maze and change it to an array of ints. You could use bit masking to store information about each flag. If you convert "#" => 0b0000, "_" => 0b0001, "-"/"+" => 0b0011, you can check if it is possible to access a neighbor by checking if self.maze[i][j] & 0b0001. You can check if you've reached your goal by doing if self.maze[i][j] & 0b0010. You can keep track of which nodes you've already visited and store that in the third bit with self.maze[i][j] |= 0b0100 and then check if you've visited a node using if self.maze[i][j] & 0b0100.

EDIT: I threw together a working example, which uses bit masking and BFS (note that to change it to DFS you only have to edit current = self.paths.popleft() to current = self.paths.pop().

import collections
import string
import time

class MazeRunner:

def __init__(self, file_path):
self.Point = collections.namedtuple('Point', 'row col parent')
self.paths = collections.deque()

with open(file_path,'r') as f:
maze = [list(line.rstrip()) for line in f.readlines()]
maze_formatted = [["#_".find(l) for l in row] for row in maze]
maze_formatted[-1] = [i*3 for i in maze_formatted[-1]]
return maze_formatted

def show_maze(self):
for row in self.maze:
s = ""
for col in row:
if str(col) in string.ascii_lowercase:
s += col
else:
s += "# "[col&0b001]
print(s)

def neighbors(self, p):
if p.row > 0 and self.maze[p.row-1][p.col] & 0b001:
yield self.Point(p.row-1, p.col, p)
if p.row < len(self.maze)-1 and self.maze[p.row+1][p.col] & 0b001:
yield self.Point(p.row+1, p.col, p)
if p.col > 0 and self.maze[p.row][p.col-1] & 0b001:
yield self.Point(p.row, p.col-1, p)
if p.col < len(self.maze)-1 and self.maze[p.row][p.col+1] & 0b001:
yield self.Point(p.row, p.col+1, p)

def solve(self):
solution_found = False
while self.paths:
current = self.paths.popleft()
if self.maze[current.row][current.col] & 0b010:
solution_found = True
print('Solution found!')
break

for point in self.neighbors(current):
if not self.maze[point.row][point.col] & 0b100:
self.paths.append(point)
self.maze[point.row][point.col] |= 0b100;

if not solution_found:
return;

final_path = []
while current:
final_path.append(current)
current = current.parent

final_path = final_path[::-1]
for i, node in enumerate(final_path):
self.maze[node.row][node.col] = string.ascii_lowercase[i%26]

def find_path(self):
start_col = self.maze.index(0b001)
start_row = 0
self.paths.append(self.Point(start_row, start_col, None))
t0 = time.clock()
self.solve()
t1 = time.clock()
print("Solution found in %.2fms" % ((t1-t0)*1000,))

def main():

path = "maze.txt"
solver = MazeRunner(path)

solver.find_path()
solver.show_maze()

if __name__ == "__main__":
main()


This code always finds the (or rather one of) the shortest paths, and is about 5-10 times faster for some larger maze examples that I've tested it with.

• Thank you, wonderful insights. The part about bit masking is interesting. I did not know that bit masking would be faster than string comparisons, I will take that into account next time I come across a similar scenario. I knew recursion wouldn't be a feasible option for larger mazes. I kinda wanted to bait them into asking me about that scalability issue though. Thank you for taking the time to write down a working example! – Apoorva Vinod Jul 10 '18 at 23:55
• In this case, the bit masking wasn't extremely helpful, even if it did provide a speedup. However, the power of masking comes when you want to check for multiple properties at once. If we use 32/64 bit integers, we can check up to 32/64 flags in a single comparison using if (number & bitmask) == magic_number (e.g. if (number & 0b10101) == 0b10001 checks if the first and fifth bit are set, and the third bit is not set). The applications can be pretty niche, but it's a great trick when applicable. – maxb Jul 11 '18 at 6:04