CODEWITHSUNDEEP
python
Andrew Zaw
Andrew Zaw

Reputation: 814

Programming Maze Solution recursively

This function is intended to recursively navigate a maze and find the length of the shortest path. The path itself is not necessary, only the length. The maze is represented by a 2d list with values such as 

0 1 0 0 0 
0 0 0 1 0
0 0 0 1 0

The user starts at (0,0) and must end up at the end of the maze as defined (in my case it is the bottom right cell). 1's represent walls. 

def maze(x,y,array,length):
    m = len(array)
    n = len(array[0])
    if x < 0 or y < 0 or x == m or y == n or array[x][y] == 1:
        return float("inf")
    elif x == m - 1 and y == n - 1:
        return length
    else:
        array[x][y] = 1
        up = maze(x - 1,y,array,length + 1)
        right = maze(x,y + 1,array,length + 1)
        down = maze(x + 1,y,array,length + 1)
        left = maze(x,y - 1,array,length + 1)
        return min(up,down,left,right)


array = [[0,1,0,0,0],[0,0,0,1,0],[0,0,0,1,0]]
minLength = maze(0,0,array,1)
print(minLength)

I designed it so that it recursively finds all possible paths from each direction (up, down, left and right), and returns the lowest value from all these paths with each step of the way. It returns inf for any path that is not valid.

For this specific array, it returns 11, which is false, it should be 9. I do not believe it is merely a mathematical error, as I tried printing each step of the way and it is not recognizing certain paths (it returns inf for paths that most definitely have options).

I can't seem to find where my code is going wrong, it seems like it should properly return the value, but in practice it does not.

Upvotes: 0

Views: 574

Answers (1)

Prune
Prune

Reputation: 77900

array is a reference to the original array, not a local copy. See any of the on-line tutorials on how Python passes function arguments, or how it handles lists. You can see the effect by printing array in your main program after the call to maze:

Final Maze [
    [1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1],
    [1, 1, 1, 1, 0]
]

Fixing this is relatively easy: copy the nested list and use that copy locally.

from copy import deepcopy

def maze(x,y,array,length):
    m = len(array)
    n = len(array[0])
    if x < 0 or y < 0 or x == m or y == n or array[x][y] == 1:
        return float("inf")
    elif x == m - 1 and y == n - 1:
        return length
    else:
        new_maze = deepcopy(array)
        new_maze[x][y] = 1
        up = maze(x - 1,y,new_maze,length + 1)
        right = maze(x,y + 1,new_maze,length + 1)
        down = maze(x + 1,y,new_maze,length + 1)
        left = maze(x,y - 1,new_maze,length + 1)
        return min(up,down,left,right)


array = [[0,1,0,0,0],[0,0,0,1,0],[0,0,0,1,0]]
minLength = maze(0,0,array,1)
print("Final Maze", array)
print(minLength)

The output from this is (edited for readability again)

Final Maze [
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 1, 0]
]
9

Upvotes: 1

Related Questions