Teknikmuseet, ugly hack

main.py

"""

We split the maze into sevent walkable regions, denoting 
the exits with 'b' for blue and 'r' for red in the following
figure.

.....................
.22222r3333333333b33.
.bb.bb.rr.....33..33.
.11r66b444444r333333.
.11.66.bb.rr......rr.
.11b6666666666666b55.
.rr.......bb.........
. 0.......77.........

       Figure 1. 

Now we can construct the graph using the notation 
'<region>_<from colour>' for vertices and edges. 

'0_red' means we are in region 0 and we are looking for
exits allowed when red was the previous colour. 

This will give the result ['1_blue'], which contains an 
edge from '0_red' to '1_blue', meaning that we will end 
up in region 1 and are only allowed to take blue exits.

Looking at '1_blue' we should be given the choices: ['2_red', '6_red'].

If we start from the end, we can work our way back.
"""

maze = {
    '0_red': ['1_blue'],
    '1_blue': ['2_red', '6_red'],
    '1_red': ['6_blue'],
    '2_red': ['3_blue'],
    '2_blue': ['1_red', '6_red'],
    '3_red': ['2_blue', '4_blue', '5_blue'],
    '3_blue': ['3_red'],
    '4_red': ['3_blue', '6_blue'],
    '4_blue': ['6_red'],
    '5_red': ['3_blue'],
    '5_blue': ['6_red'],
    '6_red': ['1_blue', '4_blue'],
    '6_blue': ['1_red', '2_red', '4_red', '7_red', '5_red'],
    '7_red': [],
}

start = '0_red'
end = '7_red'

def backtrack(graph, node):
    return [vertex for vertex in graph if node in graph[vertex]]

def find_path_by_backtrack(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not graph.has_key(start):
        return None
    for node in backtrack(maze, start):
        if node not in path:
            newpath = find_path_by_backtrack(graph, node, end, path)
            if newpath: return newpath
    return None

path = find_path_by_backtrack(maze, end, start)
path.reverse()
print(path)