Finding all maze solutions with Python

I am trying to find (using Python) all possible solutions to a maze. I have a DFS script that returns one solution. I am trying to adapt it but I'm really having a hard time wrapping my head around the whole recursion thing.

Here's the code I have, which works for finding one possible solution using DFS: Any tips or help would be much appreciated! (The "lett" in the array can be ignored/considered regular "path")

def DFS(x,y,Map):
    if (Map[x][y]=="exit"):                             #check if we're at the exit
        return [(x,y)]                                  #if so then we solved it so return this spot
    if ((Map[x][y]!="path") and (Map[x][y]!="lett")):   #if it's not a path, we can't try this spot
        return []
    Map[x][y]="explored"                                #make this spot explored so we don't try again
    for i in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:         #new spots to try
        result = DFS(i[0],i[1],Map)                     #recursively call itself
        if len(result)>0:                               #if the result had at least one element, it found a correct path, otherwise it failed
            result.append((x,y))                        #if it found a correct path then return the path plus this spot
            return result
    return []                                           #return the empty list since we couldn't find any paths from here

def GetMap():
    return [
        ["wall","wall","wall","wall","wall","wall","wall","wall"],
        ["wall","path","path","path","path","path","path","wall"],
        ["wall","wall","wall","path","wall","lett","path","wall"],
        ["wall","path","path","path","wall","wall","path","wall"],
        ["wall","path","wall","lett","path","path","path","wall"],
        ["wall","path","wall","wall","wall","wall","path","wall"],
        ["wall","path","lett","path","path","path","exit","wall"],
        ["wall","wall","wall","wall","wall","wall","wall","wall"]
    ]

def DrawMap(Map,path):
    for x in range(0,len(Map)):
        for y in range(0,len(Map[x])):
            if ((x,y) in path):
                assert Map[x][y] in ("path","lett","exit")
                print("-",end="")
            elif (Map[x][y]=="wall"):
                print("#",end="")
            elif (Map[x][y]=="exit"):
                print("e",end="")
            elif (Map[x][y]=="lett"):
                print("L",end="")
            else:
                print(' ',end="")
        print()

print("\nUnsolved:\n")
DrawMap(GetMap(),[])
print("\n")

print("Solved with DFS:")
print("path is ",len(DFS(1,1,GetMap()))," spots long\n")
DrawMap(GetMap(),DFS(1,1,GetMap()))
print("\n")

Solution 1:

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)