Maze Solver in Python

copyright.txt

Source code is copyright 2014 alex@python.code.trimtab.ca

Feel free to use and modify for commercial and non-commercial purposes.
A link back to this page must be included UNLESS the source is functionally changed.

in.txt

####################################
#S#  ##  ######## # #      #     # #
# #   #             # #        #   #
#   # ##### ## ###### # #######  # #
### # ##    ##      # # #     #### #
#   #    #  #######   #   ###    #E#
####################################

maze.py

#
# 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)

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#
####################################

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>')?

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

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#
####################################