Python Maze solving program: how to mark correct path

Question

I have written a program that solves a maze recursively. It opens a text file containing a maze, converts it into a list of lists, and then try to recursively solve it. Here's the part that solves the maze:

def search(x,y, mazeList):
    # returns True if it has found end of maze
    if mazeList[x][y] == 'E':
        return True
    # returns False if it encounters a wall
    elif mazeList[x][y] == '-':
        return False
    elif mazeList[x][y] == '+':
        return False
    elif mazeList[x][y] == "|":
        return False
    # returns False if it finds a visited path
    elif mazeList[x][y] == '*':
        return False
    # marks path with '*'
    mazeList[x][y] = '*'

    # recursive search        
    if ((search(x+1, y, mazeList))
        or (search(x, y-1, mazeList))
        or (search(x-1, y, mazeList))
        or (search(x, y+1, mazeList))):
        return True
    return False

In the maze, '-', '+' and '|' make up the walls of the maze, empty spaces can be navigated and 'E' is the end of maze. It starts from lower left part of the maze, and goes from there. I want the correct path to be marked with *, however it marks every path it takes with * even if it's the wrong path from which it backtracks.

So how can I edit my code so that in the end, only the correct path from start to finish is marked with *

Answer 1

You can try re-writing the path 'on your way back', with a symbol different from the '*' you use to make visited path.

Example: replace

if mazeList[x][y] == 'E':
        return True

with

if mazeList[x][y] == 'E':
        mazeList[x][y] = 'o'
        return True

and

if ((search(x+1, y, mazeList))
        or (search(x, y-1, mazeList))
        or (search(x-1, y, mazeList))
        or (search(x, y+1, mazeList))):
        return True

with

if ((search(x+1, y, mazeList))
        or (search(x, y-1, mazeList))
        or (search(x-1, y, mazeList))
        or (search(x, y+1, mazeList))):
        mazeList[x][y] = 'o'
        return True

Hopefully, the path will be written with o's. Did not test it though

Answer 2

In short, mark a cell as belonging to the correct path whenever you return True. You have to mark it with something other than the star. Also, once you find one of the direction that gives you true, do not try other ones. (Update: Python does support short-circuit boolean evaluation, but the following code does not rely on it.). So you could write something like:

dx = [1, -1, 0, 0]   # better define dx and dy globally 
dy = [0, 0, 1, -1]
for i in range(4):
  if search(x+dx[i], y+dy[i], mazeList):
    mazeList[x][y] = '!'
    return True
return False

The first part can be made more concise:

  if mazeList[x][y] == 'E':
    return True
  elif mazeList[x][y] != ' ':
    return False
  else:

Alternatively, you can use mazeList[x][y] in ['+', '-'].

In general, when you are doing some kind of Depth-first search, you print out the correct answer at the end of a recursive function, when you are backtracking, not when you are first entering it, as you don't know a priori, which direction is correct. Same applies e.g. to finding and printing an Euler cycle in a graph, if there is one.

Answer 3

Alternatively to "unmarking" the path, you can try this: Instead of returning just True or False, return the path you've found, then use another method to draw the marks.

When you find the "E", you simply return [(x, y)]. Your recursive search then could look like this:

for (dx,dy) in [(+1,0), (-1,0), (0,+1), (0,-1)]:
    path = search(x+dx, y+dy, mazeList)
    if path: # path is a (non-empty) list
        return [(x, y)] + path

This will gradually build and return the path to the target, from goal to start, as the recursive calls return.

Of course, since you rely on the path being marked for avoiding revisiting previous locations, you will need some other means for that, e.g. a global set of previously visited locations.

Also note that your algorithm is a depth-first-search, and will thus not find the shortest, but any path to the goal. It might be better to use a breadth-first-search for this, but this will require some major restructuring of your code, being implemented using a queue instead of recursion.