Ghost repetition structure

Question

maze = """\
##############
#            #
#            #
#   ##########
#   #       X#
#   ## ####  #
#   #     ####
#            #
##############
"""
EMPTY, BLOCK, STEP, END ,WALL=" ", "*", ".", "X", "#"
UP, DOWN, LEFT, RIGHT = "˄", "˅", "<", ">"
north, south, east, west=0, 1, 2, 3
movem = {
    north: (lambda x,y:(x, y-1)),
    south: (lambda x,y:(x, y+1)),
    east : (lambda x,y:(x-1, y)),
    west : (lambda x,y:(x+1, y))
    }

def solve(maze, x, y, move):
    found = False
    if 0 <= x < len(maze[0]) and 0 <= y < len(maze):
        if maze[y][x] == EMPTY:
            maze[y][x] = BLOCK

            if (solve(maze, x+1, y, RIGHT) or solve(maze, x, y+1, DOWN) or
                solve(maze, x-1, y, LEFT) or solve(maze, x, y-1, UP)):
                maze[y][x] = move
                found = True

        elif maze[y][x] == END:
            found = True 

    return found


if __name__ == "__main__":

    maze = [[char for char in line] for line in maze.splitlines()]
    solve(maze, 1, 4, EMPTY)

    for line in maze:      
        print("".join(line))

I saw this code on the internet, in an older version, and I decided to improve it a little bit, and that was the result(It cost me several months), now, I’m applying this same code in Astar (which is almost costing me a year), to find the minimum path, But I still don’t understand one thing, how does the Solver() function perform several times? because I don’t see any repeating structure. It would be the "working together" of the boolean variable found with the condition if __name__ == "__main__"?

site where I found the old code: [https://wiki.python.org.br/ResolvedorLabirinto]

Answer 1

This code searches for brute force in the labyrinth. He always tries to go first to the right; if it is not possible he tries to go down, but to the left and, finally, up. (Note that this is exactly a clockwise rotation)

This is brute force because he will walk blindly through the labyrinth until he finds his goal. Depending on where the goal is, it will walk through the entire maze before finding it. Basically he will test all positions until he finds the goal.

You said you didn’t understand how the function solve is executed more than once. Read carefully: It is called several times within itself, in this passage here:

if (solve(maze, x+1, y, RIGHT) or solve(maze, x, y+1, DOWN) or
    solve(maze, x-1, y, LEFT) or solve(maze, x, y-1, UP)):
    maze[y][x] = move
    found = True

See that function solve called herself by passing new parameters. That’s how she moves. Note that on the first try she passes x+1, y, ie, it moves to the right column (so I said it tries to go first to the right). If this call returns False she tries again passing x, y+1 (that is, down), if it doesn’t happen again she tries x-1, y (to the left) and, if this also does not work, she tries last on x, y-1 (up).

Calling a function within itself is a technique known as recursion.

https://en.wikipedia.org/wiki/Recursion_(computer_science)

To turn this code into an A-star you need to create a heuristic function (usually the absolute distance between the current coordinate and the goal), then you apply the heuristic to all neighboring coordinates and call the solve first for the coordinate that generated the lowest value in the heuristic.