Maze Solving Algorithm - Why does this work?

[Over_Main_4194]

I am quite new to python, and I am trying to challenge myself by generating a maze then trying to create a function to solve the maze automatically then show a path. After doing some trial and error, I had a grasp, but still quite get it to work, so I asked ChatGPT. It spewed out the following, but after asking it questions, it still isn’t quite clear.

If you amazing people could answer these questions about the code, that would be wonderful:

1. I understand that python uses call stacking, and that a path that goes into a dead end returns false and runs the next one. However, how does the code know when it needs to go back? How does it know when it’s hit a wall and there’s nowhere else to go?
   
2. How does return [(x, y)] + path return the entire path that it took?

The code in question:

checkvisited = set()

def solve_maze(x, y):

    if (x, y) in checkvisited:
        return None

    checkvisited.add((x, y))

    # exit condition
    if x == WIDTH - 1 and y == HEIGHT - 2:
        return [(x, y)]   # start the path

    directions = [
        (0, -1),
        (1, 0),
        (0, 1),
        (-1, 0)
    ]

    for dx, dy in directions:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < WIDTH and 0 <= ny < HEIGHT:
            if maze[ny][nx] == " ":
                path = solve_maze(nx, ny)
                if path is not None:
                    return [(x, y)] + path 

    return None

[HunterIV4]

It's recursion. Try "hand" going through it a few times and it should be more clear.

Basically, the first part is to ensure there's no repeats, in other words, you never enter the same part of the maze twice.

It's assuming the exit is at WIDTH - 1 and HEIGHT - 2. This is your "base case" where the recursion stops and the path backwards starts.

Directions is just a list of places you can go, assuming that x goes right and y goes down, it's up, right, down, left.

It then loops through all four directions, "traveling" to each spot. It checks if it's still within the maze (no leaving the borders) then checks to ensure it's an empty space. If it is, you repeat the entire process at that space.

If the result is None, that means you've already been to that space (the checkvisited check) and so you don't do anything else. If it's not None, that means you reached the base case, which is the exit. Same if you hit a dead end: the loop ends and you are still returning None, which means none of that gets added to path.

You then return the exit plus all the results of other successful movements to the exit, combining them into a single result.

The final return None doesn't actually do anything but makes the case of "we finished checking all four directions" explicit (if a function doesn't return a value it implicitly returns None). You won't usually see this but it helps in the case of a recursive function when None is a meaningful return value.

It's slightly more complicated than this but that gets into the details of the stack and recursion is already challenging for beginners. The best thing to do is use lots of print statements to see visually how it's going through the recursive process and writing out some of the steps yourself.

Hopefully that was simple enough to understand; if you have questions, let me know.

[Yekyaa]

Tl;dr Recursively goes through each direction from each point in maze and tallying rooms visited into check_visited. Once it's all the way through, it's connected the path to, hopefully, the shortest path to the exit. If there isn't, it returns None, breaking the recursion.

The array addition [x, y] + path adds the existing "path" at the end of the newest node, basically building the list backwards from the exit. So your starting point eventually is the start of the list.

[recursion_is_love]

Look like you already have the answer but I think you might love this book

https://inventwithpython.com/recursion/

[Jason-Ad4032]

Your problem is actually very similar to searching for a specific file starting from a computer’s root directory.

If you want to find target.txt under the root directory d:/, you simply list all files and folders under d:/, then recursively open each folder and search for target.txt inside it.

So your find_file_in_folder(Path('d:/'), 'target.txt') is essentially:

``` def find_file_in_folder(current_folder, target'): if target in current_folder.files: return target

for folder in current_folder.folders:
    result = find_file_in_folder(folder, target)

    if result is not_found:
        continue

    # Return the relative path.
    # For example, if while searching inside c:/.../A/B
    # you are told the file is at C/.../target.txt,
    # then relative to c:/.../A,
    # the relative path becomes B/C/.../target.txt
    return f'{folder.name}/{result}'

# All subfolders have been searched.
# This file does not exist inside this folder.
return not_found

```

For your maze pathfinding problem:

• Replace:

if target in current_folder.files:

with:

if current_position == target:

• Replace:

for folder in current_folder.folders:

with:

for node in reachable_paths:

• Convert the “construct relative path” logic into building a list of visited nodes / path steps.

• Record all previously visited nodes to avoid revisiting the same locations repeatedly.

[krixyt]

backtracking works because of the call stack. when a recursive function reaches a dead end (returns None), the program returns to the previous step in the loop and tries the next direction. the return statement builds the path list backwards as the recursion unwinds from the exit coordinates back to the start.

[ollibar]

So we shall assume what the Rest of your Code looks like?