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

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