# Create the maze data structure:
# You can copy-paste this from inventwithpython.com/examplemaze.txt
MAZE = """
#######################################################################
#S# # # # # # # # # #
# ##### ######### # ### ### # # # # ### # # ##### # ### # # ##### # ###
# # # # # # # # # # # # # # # # # # # #
# # # ##### # ########### ### # ##### ##### ######### # # ##### ### # #
# # # # # # # # # # # # # # # # #
######### # # # ##### # ### # ########### ####### # # ##### ##### ### #
# # # # # # # # # # # # # # # # # #
# # ##### # # ### # # ####### # # # # # # # ##### ### ### ######### # #
# # # # # # # # # # # # # # # # # # #
### # # # # ### # # ##### ####### ########### # ### # ##### ##### ### #
# # # # # # # # # # # # # # # # #
# ### ####### ##### ### ### ####### ##### # ######### ### ### ##### ###
# # # # # # # # # # # # # # # # #
### ########### # ####### ####### ### # ##### # # ##### # # ### # ### #
# # # # # # # # # # # # # # # # # #
# ### # # ####### # ### ##### # ####### ### ### # # ####### # # # ### #
# # # # # # # # # E#
#######################################################################
""".split('\n')
# Constants used in this program:
EMPTY = ' '
START = 'S'
EXIT = 'E'
PATH = '.'
# Get the height and width of the maze:
HEIGHT = len(MAZE)
WIDTH = 0
for row in MAZE: # Set WIDTH to the widest row's width.
if len(row) > WIDTH:
WIDTH = len(row)
# Make each row in the maze a list as wide as the WIDTH:
for i in range(len(MAZE)):
MAZE[i] = list(MAZE[i])
if len(MAZE[i]) != WIDTH:
MAZE[i] = [EMPTY] * WIDTH # Make this a blank row.
def printMaze(maze):
for y in range(HEIGHT):
# Print each row.
for x in range(WIDTH):
# Print each column in this row.
print(maze[y][x], end='')
print() # Print a newline at the end of the row.
print()
def findStart(maze):
for x in range(WIDTH):
for y in range(HEIGHT):
if maze[y][x] == START:
return (x, y) # Return the starting coordinates.
def solveMaze(maze, x=None, y=None, visited=None):
if x == None or y == None:
x, y = findStart(maze)
maze[y][x] = EMPTY # Get rid of the 'S' from the maze.
if visited == None:
visited = [] # Create a new list of visited points.
if maze[y][x] == EXIT:
return True # Found the exit, return True.
maze[y][x] = PATH # Mark the path in the maze.
visited.append(str(x) + ',' + str(y))
#printMaze(maze) # Uncomment to view each forward step.
# Explore the north neighboring point:
if y + 1 < HEIGHT and maze[y + 1][x] in (EMPTY, EXIT) and \
str(x) + ',' + str(y + 1) not in visited:
# RECURSIVE CASE
if solveMaze(maze, x, y + 1, visited):
return True # BASE CASE
# Explore the south neighboring point:
if y - 1 >= 0 and maze[y - 1][x] in (EMPTY, EXIT) and \
str(x) + ',' + str(y - 1) not in visited:
# RECURSIVE CASE
if solveMaze(maze, x, y - 1, visited):
return True # BASE CASE
# Explore the east neighboring point:
if x + 1 < WIDTH and maze[y][x + 1] in (EMPTY, EXIT) and \
str(x + 1) + ',' + str(y) not in visited:
# RECURSIVE CASE
if solveMaze(maze, x + 1, y, visited):
return True # BASE CASE
# Explore the west neighboring point:
if x - 1 >= 0 and maze[y][x - 1] in (EMPTY, EXIT) and \
str(x - 1) + ',' + str(y) not in visited:
# RECURSIVE CASE
if solveMaze(maze, x - 1, y, visited):
return True # BASE CASE
maze[y][x] = EMPTY # Reset the empty space.
#printMaze(maze) # Uncomment to view each backtrack step.
return False # BASE CASE
printMaze(MAZE)
solveMaze(MAZE)
printMaze(MAZE)