Maze solving with python

Question

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 direction of the path. This is the part of the code where it solves the maze:

 def solve(self,x,y):
    maze = self.maze

    #Base case  
    if y > len(maze) or x > len(maze[y]):
        return False

    if maze[y][x] == "E":
        return True 

    if  maze[y][x] != " ":
        return False


    #marking
    maze[y][x] = "o"        

    #recursive case
    if self.solve(x+1,y) == True :  #right
        return True
    if self.solve(x,y+1) == True :  #down
        return True     
    if self.solve(x-1,y) == True :  #left
        return True     
    if self.solve(x,y-1) == True :  #up
        return True     

    #Backtracking
    maze[y][x] = " "
    return False    

This is an example of an unsolved maze:

####################################
#S#  ##  ######## # #      #     # #
# #   #             # #        #   #
#   # ##### ## ###### # #######  # #
### # ##    ##      # # #     #### #
#   #    #  #######   #   ###    #E#
####################################

And this is the solved version of the same maze using the code above:

####################################
#S#  ##  ######## # #oooooo#  ooo# #
#o#ooo#    oooo     #o#   ooooo#ooo#
#ooo#o#####o##o######o# #######  #o#
### #o##oooo##oooooo#o# #     ####o#
#   #oooo#  #######ooo#   ###    #E#
####################################

The result that I want to get to is:

####################################
#S#  ##  ######## # #>>>>>v#  ^>v# #
#v#^>v#    >>>v     #^#   >>>>^#>>v#
#>>^#v#####^##v######^# #######  #v#
### #v##^>>^##>>>>>v#^# #     ####v#
#   #>>>^#  #######>>^#   ###    #E#
####################################

How is it possible to do this?

Shingle

Answer 1

#marking
maze[y][x] = "o"        

#recursive case
if self.solve(x+1,y) == True :  #right
    maze[y][x] = ">"
    return True
if self.solve(x,y+1) == True :  #down
    maze[y][x] = "v"
    return True
...

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

Indulgent

Answer 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 handled
if 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')

Viehmann

It does not work, I get this : RuntimeError: maximum recursion depth exceeded in cmp – Shingle

@AboodMufti Are you sure that the original case does not get the recursion error? Based on the way the code works, the result should be the same. – Viehmann

@AboodMufti My apologies. I found the logic error in my code and fixed it – Viehmann