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.

Answer 2

You are exploring the grid using recursion where the base case is that the GOAL is found. Each instance of solve only returns a boolean so you have lost information - the path that instance took.

Refactor so that the function returns the grid location if it is viable and the return values from an instance's decendents are accumulated.

Your conditionals will need to be rethought and you want to ensure that all paths are explored (up,down,left,right). It might be helpful to use the fact that a tuple is evaluated True in a conditional, bool((0,0)) -> True.

Finally you can either:

• accumulate all the successful paths then determine the min and max lengths when the process is done or
• evaluate successful path lengths in process and use placeholder(?) variables to keep the current max and min - this option discards path information but if you don't need that, it doesn't matter.

---

I tried to formulate that based on your current code because I presumed that you understood how your current process works and it might be easier to start from there.

You could also view the grid as a graph, each point is a node with edges to the nodes around it. You could parse the grid into a graph first then use any number of well defined algorithms to traverse the graph and find your answers. For a tree solution the root would be the starting point for the search. I don't have a lot of experience using graphs so I don't feel I can give a detailed answer for this - maybe someone will answer with a better explanation.