Finding the shortest or longest solution to a maze

Question

I am working on an assignment where I have managed the main problem and am looking into the extension exercises. Currently a map is given and all of the possible solutions to the maze are identified on a grid which is printed as follows:

    1 1 3 1 0 2 
    3 3 3 3 1 3 
    3 3 1 3 3 3 
    3 3 3 1 3 0 
    3 1 3 1 3 1 
    3 1 3 3 3 0 

Where a 0 is an empty spaces, 1 is a wall, 2 is the goal, and 3 is a visited space. The extension task is to give the shortest possible solution to the maze with any given starting point. If the starting point is a wall, then the maze can’t be solved. This is fine as well. It should be able to work for any maze given.

I don't really know where to get started with this problem. One idea was to take the sum of all the paths and finding the smallest of them, but I'm not sure how to implement this.

Currently this is my code:

EMPTY = 0
WALL = 1
GOAL = 2
VISITED = 3


def solve(grid, x, y):
    if grid[x][y] == GOAL:
        show_grid(grid)
        return True
    elif grid[x][y] == WALL:
        return False
    elif grid[x][y] == VISITED:
        return False
    else:
       # mark as visited
       grid[x][y] = VISITED

       # explore neighbors clockwise starting by going up
       if      ((x < len(grid)-1  and solve(grid, x + 1, y))
             or (y > 0            and solve(grid, x, y-1))
             or (x > 0            and solve(grid, x-1, y))
             or (y < len(grid)-1  and solve(grid, x, y+1))):
           return True
       else:
           return False


def show_grid (grid):
    for i in range(len(grid), 0, -1):
        # print("i: ", i)
        for element in grid[i-1]:
            print (element, end=" ")
        print()


def main ():
    grid =    [[EMPTY, WALL, EMPTY, EMPTY, EMPTY, EMPTY],
               [EMPTY, WALL, EMPTY, WALL, EMPTY, WALL],
               [EMPTY, EMPTY, EMPTY, WALL, EMPTY, EMPTY],
               [EMPTY, EMPTY, WALL, EMPTY, EMPTY, EMPTY],
               [EMPTY, EMPTY, EMPTY, EMPTY, WALL, EMPTY],
               [WALL, WALL, EMPTY, WALL, EMPTY, GOAL]]

    solve(grid, 0, 0)

The extension asks to print the length of the shortest path, where traversing 1 square is 1 movement. Any help with this problem is appreciated.

Answer 1

I agree with @wwii's answer, if you are exploring all the solutions, simply return the length of each successful path and then find the shortest one. This can be achieved with the following changes:

1. changing your solved function to return the path instead of true or false.
2. at each node instead of putting 3 for visited, you can put the minimum length from that node to the solution (or the origin), put -1 for wall and nodes that can't reach the solution. Nodes that can't reach the solution are essentially walls.

For example,

GOAL = 'G'
WALL = 'W'
EMPTY = 'E'


def solve(grid, x, y):
    if grid[x][y] == WALL or grid[x][y].endswith(GOAL):
        return grid[x][y]

    candidates = []
    # explore neighbors clockwise starting by going down
    if x < len(grid)-1:
        candidates.append('d' + solve(grid, x + 1, y))
    if y > 0:
        candidates.append('l' + solve(grid, x, y - 1))
    if x > 0:
        candidates.append('u' + solve(grid, x - 1, y))
    if y < len(grid)-1:
        candidates.append('r' + solve(grid, x, y + 1))

    # get rid of none solutions from candidates
    candidates = [x for x in candidates if not x.endswith(GOAL)]
    if not candidates: # if no solution, it's essentially a wall
        grid[x][y] = 'W'
    else: 
        # getting shortest path
        grid[x][y] = sorted(candidates, key=lambda x: len(x))[0]

        # for longest path use code below instead of above
        # grid[x][y] = sorted(candidates, key=lambda x: len(x))[-1]
    return grid[x][y]

If a node is visited and it goes to the goal, the value at that node can be something like 'drrurG'. This means the shortest path is going down, right*2, up, right, Goal. The direction convention is down meaning going down a row, i.e. x+1.

Granted you may have to change some other parts of the code for this to work.

---

Food for thought

The above code goes over all the possible paths. But you may not need to. There may be faster ways to get to the shortest path, as this problem is not as complicated as other general pathfinding problems.

For example, the absolutely shortest path is obviously the straight line from start to goal. Check that first. If that's not a solution, then start checking the next shortest paths. See if those work. If not, keep going until you find it.