def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first
    [2nd Edition: p 75, 3rd Edition: p 87]

    Your search algorithm needs to return a list of actions that reaches
    the goal.  Make sure to implement a graph search algorithm
    [2nd Edition: Fig. 3.18, 3rd Edition: Fig 3.7].

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print "Start:", problem.getStartState()
    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    print "Start's successors:", problem.getSuccessors(problem.getStartState())
    """
    "*** YOUR CODE HERE ***"
    from game import Directions
    startNode = (problem.getStartState(),'None',1)
    path =  recDFS(problem, Tree(problem, None, startNode), [[],False])
    direction = []
    for p in path[0]:

        direction.append( p[1] )
    return direction
    #return ['North','North','West','East','West','East','West','West','West','West','North','North','West']
    #util.raiseNotDefined()



def recDFS(problem, tree, path):
    #print "\n\n"
    #print path
    if path[1]:
        return path
    if tree == None:
        return path
    for child in tree.children:
        if child in path[0]:
            tree.children.remove(child)


    if (problem.isGoalState(tree.node[0])):
        path[1] = True
        return path
#   if tree.node[1] != 'None':
        #path.append(tree.node[1])
    if (len(tree.children)==0):
        path[0].pop()
        if tree.parent != None:
            tree.parent.children.remove(tree.node)
        return recDFS(problem, tree.parent, path)



    #(parent,node,[children])



    for child in tree.children:
        path[0].append(child)

        recDFS(problem,Tree(problem,tree,child),path)


    return path



class Tree:
    def __init__(self, problem, parent, node):

        self.problem = problem
        self.node = node
        self.parent = parent
        self.children = self.getChildren(node)

        #print node, " ", self.children

    def getChildren(self, node):
        children = self.problem.getSuccessors(node[0])
        for child in children:
            if self.opposite(node[1],child[1]):
                children.remove(child)

        return children

    def opposite(self, d1,d2):

        if (d1=='North' and d2=='South'):
            return True
        if (d1=='West' and d2=='East'):
            return True
        if (d1=='South' and d2=='North'):
            return True
        if (d1=='East' and d2=='West'):
            return True
        return False