Unit Four Maze Solver | Python Fiddle

# ----------
# User Instructions:
#
# Define a function, search() that takes no input
# and returns a list
# in the form of [optimal path length, x, y]. For
# the grid shown below, your function should output
# [11, 4, 5].
#
# If there is no valid path from the start point
# to the goal, your function should return the string
# 'fail'
# ----------

# Grid format:
#   0 = Navigable space
#   1 = Occupied space

grid = [[0, 0, 1, 0, 0, 0], # The maze to find a solution to
        [0, 0, 1, 0, 0, 0],
        [0, 0, 0, 0, 1, 0],
        [0, 0, 1, 1, 1, 0],
        [0, 0, 0, 0, 1, 0]]

checked = [[0 for i in range(len(grid[0]))] # Checked cells grid;
           for j in range(len(grid))]       # initially all zeros

init = [0, 0] # Start cell

# Make sure that the goal definition stays in the function.
goal = [len(grid)-1, len(grid[0])-1]

delta = [[-1, 0 ], # go up
        [ 0, -1], # go left
        [ 1, 0 ], # go down
        [ 0, 1 ]] # go right

delta_name = ['^', '<', 'v', '>'] # Do not use these initially

# "Number of steps" to add to each additional cell in the solution path;
# All the same at this time
cost = 1

# Call this function to start the process
def search():
    if (init[0] == goal[0]) and (init[1] == goal[1]):
        print [0, init[0], init[1]]
        return
    searchHelper([[0, init[0], init[1]]])
    return

def searchHelper(openCells):
    if len(openCells) == 0:
        print 'fail'
        return
    lowCell = getLowG(openCells)
    if (lowCell[1] == goal[0]) and (lowCell[2] == goal[1]):
        print lowCell
        return
    openCells += generateExpansion(lowCell) # Get list of next possible cells to search
    checked[lowCell[1]][lowCell[2]] = 1 # We will be expanding this cell; mark it as checked
    tempOpenCells = []
    # Remove any checked cells from the expanded cells list
    for i in range(len(openCells)):
        if checked[openCells[i][1]][openCells[i][2]] == 0:
            tempOpenCells.append(openCells[i])
    openCells = tempOpenCells
    searchHelper(openCells)

def getLowG(openCells):
    lowCandidate = [openCells[0]] # Assume the first entry will be the lowest G-Value
    lowNumber = openCells[0][0] # Get the first entry's G-Value
    for i in range(len(openCells)): # Prepare to check all G-Values
        if openCells[i][0] <= lowNumber: # If the current G-Value is lower than current lowNumber
            if checked[openCells[i][1]][openCells[i][2]] == 0: # And the current cell is not already checked
                lowNumber = i # Take the current G-Value as the new lowNumber
                lowCandidate.append(openCells[i]) # AND add the current cell to the list of candidates
    for i in range(len(lowCandidate)-1): # remove all but the last of the candidates; last one IS (one of the) lowest G-Values
        del(lowCandidate[0])
    return lowCandidate[0] # Return the only cell left in the list (the or one of the lowest G-Values

def generateExpansion(startCell):
    expandCells = []
    for i in range(len(delta)): # For each possible direction of motion
        testX = startCell[1] + delta[i][0] # Calculate the new X
        testY = startCell[2] + delta[i][1] # Calculate the new Y
        if (testX > -1) and (testX < len(grid)): # If X stays in bounds
            if (testY > -1) and (testY > -1) and (testY < len(grid[0])): # If Y stays in bounds
                if checked[testX][testY] == 0: # If the new cell has not already been checked
                    if (grid[testX][testY]) == 0: # Finaly , if the cell is not a wall in the maze
                        expandCells.append([startCell[0] + 1, testX, testY])
    return expandCells

search()

Python Fiddle

Python Cloud IDE