dfs.py

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

  fringe = util.Stack()
  closed = set()

  def makeNode(state, prevActions=[], action=False):
      actions = []
      if action in ( n, s, w, e ):
          actions = prevActions + [action]
      return ( state, actions )

  def search(fringe):
      if fringe.isEmpty():
          raise Exception, 'depthFirstSearch could not find solution'
      node = fringe.pop()
      if problem.isGoalState(node[0]):
          return node[1]
      if node[0] not in closed:
          closed.add(node[0])
          for triple in problem.getSuccessors(node[0]):
              fringe.push(makeNode(triple[0], node[1], triple[1]))
      return search(fringe)

  fringe.push(makeNode(problem.getStartState()))

  return search(fringe)