Skip to content

Instantly share code, notes, and snippets.

@a613 a613/copyright.txt
Last active May 27, 2020

Embed
What would you like to do?
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

This comment has been minimized.

Copy link
Owner Author

a613 commented Mar 28, 2020

If the entire path is desired, not just the position of the end symbol, the solver can be modified to build up the list as it goes, by making these changes:

-       also written. The return value is None if no solution was
-       found, and a (row_index, column_index) tuple when a solution
-       is found."""
+       also written. The return value is an empty list if no solution was
+       found, and a list of symbols along a valid solution path 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
+        return []
    if maze.get(where) == end_symbol:
        # standing on the end cell
-        return where
+        return [end_symbol]
    if maze.get(where) not in (vacant_symbol, start_symbol):
        # somebody has been here
-        return
+        return []

    for direction in directions:
-        next_cell = map(operator.add, where, direction)
+        next_cell = list(map(operator.add, where, direction))  # added `list()` for Python 3

        # 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
+            is_first_step = maze.get(where) == start_symbol
+            return ([start_symbol] if is_first_step else []) +\
+                   ([] if is_first_step else [marker]) +\  # make this line simply `[marker]` to include the initial step
+                   sub_solve

    # no directions worked from here - have to backtrack
    maze.set(where, backtrack_symbol)
+    return []

Example output:

Found path through maze ['S', 'v', '>', '>', '^', '>', '>', 'v', 'v', 'v', '>', '>', '>', '^', '>', '>', '>', '^', '^', '>', '>', '>', 'v', 'v', '>', '>', '>', '>', '>', 'v', '>', '>', '^', '^', '^', '^', '>', '>', '>', '>', '>', 'v', '>', '>', '>', '>', '^', '>', '>', 'v', '>', '>', 'v', 'v', 'v', 'E']
####################################
#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
You can’t perform that action at this time.