Finding all maze solutions with Python

by

wishful thinking

The onset of a problem like this can feel overwhelming, but my favourite technique in programming makes complexity vanish into thin air. Using wishful thinking, we write our program how we wish it could be, then we make our wishes come true –

# simple.py

from maze import maze
from cursor import cursor

def dfs(cursor, maze):
  q = maze.get(cursor.y(), cursor.x())
  if not q or q.is_wall() or q.is_step():
    return
  elif q.is_exit():
    yield maze
  else:
    next_maze = maze.step(cursor.y(), cursor.x())
    yield from dfs(cursor.up(), next_maze)
    yield from dfs(cursor.down(), next_maze)
    yield from dfs(cursor.right(), next_maze)
    yield from dfs(cursor.left(), next_maze)

def solve(cursor, maze):
  for x in dfs(cursor, maze):
    return x

All we need to get going is a maze, m, and a cursor, c –

# simple.py (continued)

# read maze from file
m = maze.from_file("./input")

# initialize cursor
c = cursor.from_ints(1, 1)

We can find the first solution using solve –

# simple.py (continued)

print(solve(c, m))

########
#---   #
###-#L #
#  -## #
# #----#
# ####-#
# L   e#
########

Or we can find all solutions using dfs –

# simple.py (continued)

for x in dfs(c, m):
  print(x, end="\n\n")

(output below reformatted to save space)

########   ########   ########   ########   ########   ########
#---   #   #---   #   #----- #   #----- #   #------#   #------#
###-#L #   ###-#L #   ### #--#   ### #--#   ### #L-#   ### #L-#
#  -## #   #---## #   #   ##-#   #---##-#   #   ##-#   #---##-#
# #----#   #-#L   #   # #L  -#   #-#----#   # #L  -#   #-#----#
# ####-#   #-#### #   # ####-#   #-#### #   # ####-#   #-#### #
# L   e#   #-----e#   # L   e#   #-----e#   # L   e#   #-----e#
########   ########   ########   ########   ########   ########

cursor

To make the program above work, we need to fulfill all of our wishes. We’ll start with the cursor module. A cursor is simply a pair of integers that gives us a convenient up, down, left, and right movements –

# cursor.py

def from_ints(y, x):
  return (y, x)

def up(t):
  (y, x) = t
  return from_ints(y - 1, x)

def down(t):
  (y, x) = t
  return from_ints(y + 1, x)

def left(t):
  (y, x) = t
  return from_ints(y, x - 1)

def right(t):
  (y, x) = t
  return from_ints(y, x + 1)

def to_str(t):
  (y, x) = t
  return f"({y}, {x})"

As you can see, we are working with ordinary functions. Python has nice object-oriented features too and we wish to extend such conveniences to the users of our module. We easily add an OOP interface by wrapping the plain functions –

# cursor.py (continued)

class cursor:
  def from_ints(y, x): return cursor(from_ints(y, x))
  def __init__(self, t): self.t = t
  def __iter__(self): yield from self.t
  def __str__(self): return to_str(self.t)
  def up(self): return cursor(up(self.t))
  def down(self): return cursor(down(self.t))
  def right(self): return cursor(right(self.t))
  def left(self): return cursor(left(self.t))

maze

Now we move onto our maze module. We’ll start by writing ordinary functions to convert from_file to a maze, and from a maze to_str –

# maze.py

from cell import cell

def from_file(filename):
  with open(filename) as f:
    return from_str(f.read())

def from_str(s):
  return [ list(map(cell.from_str, row)) for row in s.split("\n") ]

def to_str(t):
  return "\n".join("".join(map(str, row)) for row in t)

As a bonus, notice how we got from_str for free. Next we write functions to get or set a cell using y and x coordinates. Here we also write step, a simple wrapper around set, which is used to mark that a cell in the maze has been explored –

# maze.py (continued)

from arr_ext import update

def get(t, y, x):
  try:
    if x < 0 or y < 0:
      return None
    else:
      return t[y][x]
  except IndexError:
    return None

def set(t, y, x, v):
  return update \
    ( t
    , y
    , lambda row: update(row, x, lambda _: v)
    )

def step(t, y, x):
  return set(t, y, x, cell.step())

Don’t be afraid to make as many wishes as you want. We’ll implement update when we need it. And just like we did in the previous module, we add the object-oriented interface –

# maze.py (continued)

class maze:
  def from_file(filename): return maze(from_file(filename))
  def from_str(s): return maze(from_str(s))
  def __init__(self, t): self.t = t
  def __iter__(self): yield from self.t
  def __str__(self): return to_str(self.t)
  def get(self, y, x): return get(self.t, y, x)
  def set(self, y, x, v): return maze(set(self.t, y, x, v))
  def step(self, y, x): return maze(step(self.t, y, x))

cell

When we wrote the Maze module, we wished for a cell module. The technique of wishful thinking should be coming into focus now: make a wish, fulfill it. Our Cell module represents a cell in our maze. We start with a way to convert from_str to a cell, and from a cell to_str –

# cell.py

wall = 0
path = 1
exit = 2
lett = 3
step = 4

str_to_cell = \
  { "#": wall, " ": path, "e": exit, "L": lett, "-": step }

cell_to_str = \
  { v: k for (k, v) in str_to_cell.items() }

def from_str(s):
  if s in str_to_cell:
    return str_to_cell[s]
  else:
    raise RuntimeError(f"invalid cell character: {s}")

def to_str(t):
  if t in cell_to_str:
    return cell_to_str[t]
  else:
    raise RuntimeError(f"invalid cell component: {t}")

Additionally we write is_* predicates to determine whether a cell is a wall, a path, etc. This highlights a strength of abstraction: we can change how our data is represented in one module without having to modify other modules in our program –

# cell.py (continued)

def is_wall(t): return t == wall
def is_path(t): return t == path
def is_exit(t): return t == exit
def is_lett(t): return t == lett
def is_step(t): return t == step

Add the object-oriented interface. Again, it’s a simple wrapper around our plain functions –

# cell.py (continued)

class cell:
  def from_str(s): return cell(from_str(s))
  def wall(): return cell(wall)
  def path(): return cell(path)
  def exit(): return cell(exit)
  def lett(): return cell(lett)
  def step(): return cell(step)
  def __init__(self, t): self.t = t
  def __str__(self): return to_str(self.t)
  def is_wall(self): return is_wall(self.t)
  def is_path(self): return is_path(self.t)
  def is_exit(self): return is_exit(self.t)
  def is_lett(self): return is_lett(self.t)
  def is_step(self): return is_step(self.t)

arr_ext

Only one wish left to fulfill! We write the generic update function in an Array Extensions module, arr_ext –

# arr_ext.py

def update(t, pos, f):
  try:
    return [ *t[:pos], f(t[pos]), *t[pos + 1:]]
  except IndexError:
    return t

advanced

Our simple program solves the problem in a simplified way. What if we want to solve the maze and know the path for each solution? Let’s write an advanced program below –

# advanced.py

from maze import maze
from cursor import cursor

def dfs(cursor, maze, path=[]):
  q = maze.get(*cursor)
  if not q or q.is_wall() or q.is_step():
    return
  elif q.is_exit():
    yield (maze, path)
  else:
    next_maze = maze.step(*cursor)
    next_path = [*path, cursor]
    yield from dfs(cursor.up(), next_maze, next_path)
    yield from dfs(cursor.down(), next_maze, next_path)
    yield from dfs(cursor.right(), next_maze, next_path)
    yield from dfs(cursor.left(), next_maze, next_path)

def solve(cursor, maze):
  for x in dfs(cursor, maze):
    return x

Notice how the advanced solution is just a small adjustment of the simple module. Let’s see what the first solved maze looks like –

# advanced.py (continued)

print(solution(solve(c, m)))

########
#---   #
###-#L #
#  -## #
# #----#
# ####-#
# L   e#
########
(1, 1)->(1, 2)->(1, 3)->(2, 3)->(3, 3)->(4, 3)->(4, 4)->(4, 5)->(4, 6)->(5, 6)

Now let’s see all of the solved mazes and paths –

# advanced.py (continued)

for x in dfs(c, m):
  print(solution(x), end="\n\n")

########
#---   #
###-#L #
#  -## #
# #----#
# ####-#
# L   e#
########
(1, 1)->(1, 2)->(1, 3)->(2, 3)->(3, 3)->(4, 3)->(4, 4)->(4, 5)->(4, 6)->(5, 6)

########
#---   #
###-#L #
#---## #
#-#L   #
#-#### #
#-----e#
########
(1, 1)->(1, 2)->(1, 3)->(2, 3)->(3, 3)->(3, 2)->(3, 1)->(4, 1)->(5, 1)->(6, 1)->(6, 2)->(6, 3)->(6, 4)->(6, 5)

########
#----- #
### #--#
#   ##-#
# #L  -#
# ####-#
# L   e#
########
(1, 1)->(1, 2)->(1, 3)->(1, 4)->(1, 5)->(2, 5)->(2, 6)->(3, 6)->(4, 6)->(5, 6)

########
#----- #
### #--#
#---##-#
#-#----#
#-#### #
#-----e#
########
(1, 1)->(1, 2)->(1, 3)->(1, 4)->(1, 5)->(2, 5)->(2, 6)->(3, 6)->(4, 6)->(4, 5)->(4, 4)->(4, 3)->(3, 3)->(3, 2)->(3, 1)->(4, 1)->(5, 1)->(6, 1)->(6, 2)->(6, 3)->(6, 4)->(6, 5)

########
#------#
### #L-#
#   ##-#
# #L  -#
# ####-#
# L   e#
########
(1, 1)->(1, 2)->(1, 3)->(1, 4)->(1, 5)->(1, 6)->(2, 6)->(3, 6)->(4, 6)->(5, 6)

########
#------#
### #L-#
#---##-#
#-#----#
#-#### #
#-----e#
########
(1, 1)->(1, 2)->(1, 3)->(1, 4)->(1, 5)->(1, 6)->(2, 6)->(3, 6)->(4, 6)->(4, 5)->(4, 4)->(4, 3)->(3, 3)->(3, 2)->(3, 1)->(4, 1)->(5, 1)->(6, 1)->(6, 2)->(6, 3)->(6, 4)->(6, 5)

Don’t forget to fulfill your wishes! We can see the emergence of a new module, solution, happening, but this time we will just leave it in the same file –

# advanced.py (continued)

def to_str(t):
  (maze, path) = t
  return str(maze) + "\n" + "->".join(map(str, path))

class solution:
  def __init__(self, t): self.t = t
  def __str__(self): return to_str(self.t)

More Related Contents:

  1. Why does my recursive function return None?
  2. What is the maximum recursion depth in Python, and how to increase it?
  3. Recursive function returning none in Python [duplicate]
  4. Loop through all nested dictionary values?
  5. Find all occurrences of a key in nested dictionaries and lists
  6. Python recursion with list returns None [duplicate]
  7. Basics of recursion in Python
  8. Return in Recursive Function
  9. Python: Maximum recursion depth exceeded
  10. recursive iteration through nested json for specific key in python
  11. Recursion and return statements
  12. python recursion return None type
  13. How to flatten a nested JSON recursively, with flatten_json
  14. How to recursively find specific key in nested JSON?
  15. Using self.xxxx as a default parameter – Python
  16. Recursive function returning none? [duplicate]
  17. Representing and solving a maze given an image
  18. Setting property causes maximum recursion depth exceeded
  19. How to find common elements in list of lists?
  20. python recursive vectorization with timeseries
  21. Python: using a recursive algorithm as a generator
  22. Generate all possible lists of length N that sum to S in Python
  23. How can a recursive regexp be implemented in python?
  24. Adding collision to maze walls
  25. python recursive function that prints from 0 to n?
  26. Python: maximum recursion depth exceeded while calling a Python object
  27. Recursive Typing in Python 3.5+ [duplicate]
  28. Python Array Rotation
  29. Cross product of sets using recursion
  30. Given a list of elements in lexicographical order (i.e. [‘a’, ‘b’, ‘c’, ‘d’]), find the nth permutation – Average time to solve?

Leave a Comment