Skip to content

Instantly share code, notes, and snippets.

@a613
Last active November 26, 2023 16:41
Show Gist options
  • Save a613/49d65dc30e98c165d567 to your computer and use it in GitHub Desktop.
Save a613/49d65dc30e98c165d567 to your computer and use it in GitHub Desktop.
Maze Solver in Python
####################################
#S# ## ######## # # # # #
# # # # # # #
# # ##### ## ###### # ####### # #
### # ## ## # # # #### #
# # # ####### # ### #E#
####################################
#
# Maze Solver 1.0
# March 2014
# alex@python.code.trimtab.ca
#
# Solves a maze stored in a text file, and outputs the solution
# path to a second text file in the same format.
#
# Required command-line arguments: <input_file> <output_file>
# Example usage:
#
# <in.txt>
# ####################################
# #S# ## ######## # # # # #
# # # # # # # #
# # # ##### ## ###### # ####### # #
# ### # ## ## # # # #### #
# # # # ####### # ### #E#
# ####################################
#
# python maze.py in.txt out.txt
#
# <out.txt>
# ####################################
# #S# ## ########.#.#>>>>>v# >>v# #
# #v#>>v# >>>v.....#^# >>>>^#>>v#
# #>>^#v#####^##v######^# ####### #v#
# ###.#v##>>>^##>>>>>v#^# # ####v#
# #...#>>>^#..#######>>^# ### #E#
# ####################################
#
import operator
import sys
class Maze(object):
"""Represents a two-dimensional maze, where each cell can hold a
single marker."""
def __init__(self):
self.data = []
def read_file(self, path):
"""Read a maze text file and split out each character. Return
a 2-dimensional list where the first dimension is rows and
the second is columns."""
maze = []
with open(path) as f:
for line in f.read().splitlines():
maze.append(list(line))
self.data = maze
def write_file(self, path):
"""Write the specified 2-dimensional maze to the specified
file, writing one line per row and with columns
side-by-side."""
with open(path, 'w') as f:
for r, line in enumerate(self.data):
f.write('%s\n' % ''.join(line))
def find(self, symbol):
"""Find the first instance of the specified symbol in the
maze, and return the row-index and column-index of the
matching cell. Return None if no such cell is found."""
for r, line in enumerate(self.data):
try:
return r, line.index('S')
except ValueError:
pass
def get(self, where):
"""Return the symbol stored in the specified cell."""
r, c = where
return self.data[r][c]
def set(self, where, symbol):
"""Store the specified symbol in the specified cell."""
r, c = where
self.data[r][c] = symbol
def __str__(self):
return '\n'.join(''.join(r) for r in self.data)
def solve(maze, where=None, direction=None):
"""Finds a path through the specified maze beginning at where (or
a cell marked 'S' if where is not provided), and a cell marked
'E'. At each cell the four directions are tried in the order
RIGHT, DOWN, LEFT, UP. When a cell is left, a marker symbol
(one of '>', 'v', '<', '^') is written indicating the new
direction, and if backtracking is necessary, a symbol ('.') is
also written. The return value is None if no solution was
found, and a (row_index, column_index) tuple when a solution
is found."""
start_symbol = 'S'
end_symbol = 'E'
vacant_symbol = ' '
backtrack_symbol = '.'
directions = (0, 1), (1, 0), (0, -1), (-1, 0)
direction_marks = '>', 'v', '<', '^'
where = where or maze.find(start_symbol)
if not where:
# no start cell found
return
if maze.get(where) == end_symbol:
# standing on the end cell
return where
if maze.get(where) not in (vacant_symbol, start_symbol):
# somebody has been here
return
for direction in directions:
next_cell = map(operator.add, where, direction)
# spray-painting direction
marker = direction_marks[directions.index(direction)]
if maze.get(where) != start_symbol:
maze.set(where, marker)
sub_solve = solve(maze, next_cell, direction)
if sub_solve:
# found solution in this direction
return sub_solve
# no directions worked from here - have to backtrack
maze.set(where, backtrack_symbol)
if __name__ == '__main__':
if len(sys.argv) < 3:
print 'Arguments: <input file> <output file>'
sys.exit(1)
input_file, output_file = sys.argv[1:3]
maze = Maze()
maze.read_file(input_file)
solution = solve(maze)
if solution:
print 'Found end of maze at %s' % solution
else:
print 'No solution (no start, end, or path)'
print maze
maze.write_file(output_file)
@a613
Copy link
Author

a613 commented Mar 9, 2021

In case anyone grabs the original code and gets an error when running it with Python 3, you'll need to update it with 2 changes to make it compatible with Python 3.

  1. add parentheses around the arguments to the 4 print functions, i.e. instead of print maze, make it print(maze)
  2. replace map(operator.add, where, direction) with list(map(operator.add, where, direction))

Alternatively (and even simpler) just run 2to3 -w maze.py to convert it in a single shot.

If you don't do these changes, when you run python maze.py in.txt out.txt there will an error printed:

SyntaxError: Missing parentheses in call to 'print'. Did you mean print('Arguments: <input file> <output file>')?

@1994markojovanovic
Copy link

still getting an error, a window pops up and closes immediately

@a613
Copy link
Author

a613 commented Nov 26, 2023

still getting an error, a window pops up and closes immediately

Please try running the command in a terminal, if you are on Windows and you run the python program directly it will not allow you to provide arguments and you also won't get to see output.

  1. Run a terminal/console
  2. Run 2to3 -w maze.py to convert the Python 2 code to Python 3 code
  3. Run python3 maze.py in.txt out.txt and you'll see this output:
Found end of maze at [5, 34]
####################################
#S#  ##  ########.#.#>>>>>v#  >>v# #
#v#>>v#    >>>v.....#^#   >>>>^#>>v#
#>>^#v#####^##v######^# #######  #v#
###.#v##>>>^##>>>>>v#^# #     ####v#
#...#>>>^#..#######>>^#   ###    #E#
####################################

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment