Maze Solving With Python

I am trying to make a maze solver, and it is working except that instead of the path being marked by 'o' I want it to be marked with '>', '<', 'v', '^' depending on the direc

Solution 1:

#marking
maze[y][x] = "o"#recursive caseifself.solve(x+1,y) == True :  #right
    maze[y][x] = ">"returnTrueifself.solve(x,y+1) == True :  #down
    maze[y][x] = "v"returnTrue
...

From Lix example. You need to uncomment maze[y][x] = "o", you need that row to prevent the node from being revisited

Solution 2:

I would suggest that instead of setting the value to 'o' immediately and returning 'True' you use if ... elif to set the character and then return.

@marqs pointed out that my original answer would have allowed the recursion to revisit a position that had already been proven false. As a result, mark all positions with 'o' so that they cannot be revisited and later loop through and reset all 'o' as ' '

Note that I am suggesting if ... elif since four separate if's will always check the other possibilities even though they would have been proven false by already finding the true path.

# tag = ' '  Mistake on my part
tag = 'o'# Mark so will not be revisited
maze[y, x] = tag # Mark maze point as handledif self.solve(x+1,y) == True :  #right
    tag = '>'elif self.solve(x,y+1) == True :  #down
    tag = 'v'elif self.solve(x-1,y) == True :  #left
    tag = '<'elif self.solve(x,y-1) == True :  #up
    tag = '^'else:
  # All possible paths from here are false, back up and clear this point.
  tag = ' '# Note that if none of the tests were true, tag is left as ' '
maze[y, x] = tag # Note C or C++ would use [x, y]return (tag != ' ')

This will cause the attempted (false) path to fill up with 'o' and then back up to blank when it is shown as untrue.

Alternatively, you can leave it with a 'o' in it and after the true path has been found, go back over the entire maze and clear thos points marked with 'o'

If this is the case remove the else: and change the return to

return (tag != 'o')