Maze Solution

input.txt

._._._._._._._._._.E.
| ._._._. | . ._._. |
|_._. |_. |_| | . | |
|_. |_. |_._._| |_._|
| |_._._| . ._| |_. |
| ._._._. |_| ._| ._|
| | ._. |_| ._|_._. |
| ._| |_. |_._._. | |
|_._. | | | ._. |_. |
| ._|_. | | | |_. | |
|S._._._|_._._._|_._|

maze.py

#!/usr/bin/python

f = open('maze.txt', 'r')
maze = []
s = None
e = None

for y, line in enumerate(f):
    row = []
    prow = []
    for x, char in enumerate(line):
        if char in ['\n']:
            pass
        elif char in [' ', 'E', 'S']:
            row += [1]
            prow += [1]
            if char == 'S':
                s = [x, y * 2]
            elif char == 'E':
                e = (x, y * 2)
        elif char in ['.', '_']:
            row += [0]
            prow += [1]
        elif char in ['|']:
            row += [0]
            prow += [0]
    if y != 0:
        maze += [prow]
    maze += [row]

def go(src, x, y, path):
    # OOB?
    if x < 0 or x > len(maze[0]) - 1 or y < 0 or y > len(maze) - 1:
        return []
    # Wall?
    if not maze[y][x]:
        return []
    if (x, y) == e:
        return path

    path += [(x, y)]

    rest = []
    if src != 'n':
        rest += [go('s', x, y+1, path[:])]
    if src != 's':
        rest += [go('n', x, y-1, path[:])]
    if src != 'e':
        rest += [go('w', x+1, y, path[:])]
    if src != 'w':
        rest += [go('e', x-1, y, path[:])]

    for answer in rest:
        if answer:
            return answer

    return []

soln = go('n', s[0], s[1], [])
soln += [e]

for coord in soln:
    maze[coord[1]][coord[0]] = 5

for line in maze:
    str = ''
    for val in line:
        if val == 0:
            str += 'x '
        elif val == 1:
            str += '  '
        elif val == 5:
            str += '. '
    print str

oop_maze.py

#!/usr/bin/python
from operator import add, neg

SKIP = -1
SOLID = 0
OK = 1
PATH = 2

NONE = 0
START = 1
END = 2

KEY = { # (top, bot, status)
    '\n': (SKIP, SKIP, NONE),
    'S': (OK, OK, START),
    'E': (OK, OK, END),
    ' ': (OK, OK, NONE),
    '.': (OK, SOLID, NONE),
    '_': (OK, SOLID, NONE),
    '|': (SOLID, SOLID, NONE),
}

DIRS = {
    'N': (0, -1),
    'S': (0, 1),
    'E': (1, 0),
    'W': (-1, 0),
}

PRINT = {
    SOLID: 'x',
    OK: ' ',
    PATH: '.',
}

class Maze():

    def __init__(self, string):
        self.maze = []
        for y, line in enumerate(string.split('\n')):
            prev = []
            cur = []
            for x, char in enumerate(line):
                prev += [KEY[char][0]]
                cur += [KEY[char][1]]

                if KEY[char][2] == START:
                    self.start = (x, y*2)
                elif KEY[char][2] == END:
                    self.end = (x, y*2)
            self.maze += ([prev] if y else []) + [cur]

    def inmaze(self, coord):
        return 0 <= coord[0] < len(self.maze[0]) and \
               0 <= coord[1] < len(self.maze)

    def cango(self, coord):
        return self.maze[coord[1]][coord[0]]

    def go(self, src, to, path):
        # Invalid?
        if not self.inmaze(to) or not self.cango(to):
            return []

        path += [to]

        # Reached the end?
        if to == self.end:
            return path

        try:
            # Check everywhere else
            return next(future for future in [
                self.go(DIRS[key], tuple(map(add, DIRS[key], to)), path[:])
                for key in DIRS if tuple(map(neg, DIRS[key])) != src
            ] if future)
        except StopIteration:
            # No answer
            return []

    @property
    def solution(self):
        return self.go(None, self.start, [])

    @property
    def solved_maze(self):
        result = self.maze[:]
        for coord in self.solution:
            result[coord[1]][coord[0]] = PATH
        return result

    def print_solved(self):
        print '\n'.join(
            [' '.join(
                [PRINT[val] for val in line]
            ) for line in self.solved_maze]
        )

Maze(''.join(open('maze.txt', 'r').readlines())).print_solved()

output.txt

x x x x x x x x x x x x x x x x x x x . x 
x                   x                 . x 
x   x x x x x x x   x   x   x x x x x . x 
x           x       x   x   x . . . x . x 
x x x x x   x x x   x x x   x . x . x . x 
x       x       x           x . x . . . x 
x x x   x x x   x x x x x x x . x x x x x 
x   x           x           x . x       x 
x   x x x x x x x   x   x x x . x x x   x 
x                   x   x . . . x       x 
x   x x x x x x x   x x x . x x x   x x x 
x   x . . . . . x   x . . . x           x 
x   x . x x x . x x x . x x x x x x x   x 
x . . . x   x . . . x . . . . . . . x   x 
x . x x x   x x x . x x x x x x x . x   x 
x . . . . . x   x . x . . . . . x . . . x 
x x x x x . x   x . x . x x x . x x x . x 
x       x . . . x . x . x   x . . . x . x 
x   x x x x x . x . x . x   x x x . x . x 
x . . . . . . . x . . .         x . . . x 
x . x x x x x x x x x x x x x x x x x x x