visited = []
    parent = {}
    parent[problem.getStartState()] = -1
    stack = util.Stack()
    stack.push(problem.getStartState())
    goal = problem.getStartState()

    while not stack.isEmpty():
        vertex = stack.pop()
        visited.append(vertex)

        if problem.isGoalState(vertex):
            goal = vertex
            break

        for obj in problem.getSuccessors(vertex):
            if obj[0] not in visited:
                stack.push(obj[0])
                parent[obj[0]] = vertex

    from game import Directions
    s = Directions.SOUTH
    w = Directions.WEST
    e = Directions.EAST
    n = Directions.NORTH

    action_list = []
    while parent[goal] != -1:
        if parent[goal][0] < goal[0]:
            action_list.insert(0, e)
        elif parent[goal][0] > goal[0]:
            action_list.insert(0, w)
        elif parent[goal][1] < goal[1]:
            action_list.insert(0, n)
        elif parent[goal][1] > goal[1]:
            action_list.insert(0, s)

        goal = parent[goal]

    return action_list