Able to find path using DFS but not able specify the right directions to Pacman _ Python

Question

I am working on an assignment found on an AI course page at berkley website for fun. I need to write a depth-first search for the pacman game so that it can find its path.The problem is the pacman gets stuck. I'll paste the code first to make what I am saying more clear :

import util

class SearchProblem:
  """
  This class outlines the structure of a search problem, but doesn't implement
  any of the methods (in object-oriented terminology: an abstract class).

  You do not need to change anything in this class, ever.
  """

  def getStartState(self):
     """
     Returns the start state for the search problem 
     """
     util.raiseNotDefined()

  def isGoalState(self, state):
     """
       state: Search state

     Returns True if and only if the state is a valid goal state
     """
     util.raiseNotDefined()

  def getSuccessors(self, state):
     """
       state: Search state

     For a given state, this should return a list of triples, 
     (successor, action, stepCost), where 'successor' is a 
     successor to the current state, 'action' is the action
     required to get there, and 'stepCost' is the incremental 
     cost of expanding to that successor
     """
     util.raiseNotDefined()

  def getCostOfActions(self, actions):
     """
          actions: A list of actions to take

     This method returns the total cost of a particular sequence of actions.  The sequence must
     be composed of legal moves
     """
     util.raiseNotDefined()


def tinyMazeSearch(problem):
  """
      Returns a sequence of moves that solves tinyMaze.  For any other
  maze, the sequence of moves will be incorrect, so only use this for tinyMaze
  """
  from game import Directions
  s = Directions.SOUTH
  w = Directions.WEST
  return  [s,s,w,s,w,w,s,w]

def depthFirstSearch(problem):

  """
  Search the deepest nodes in the search tree first [p 74].

  Your search algorithm needs to return a list of actions that reaches
  the goal.  Make sure to implement a graph search algorithm [Fig. 3.18].

  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 ***


  start = [problem.getStartState()]
  for item in start:
      Open=[item]
  State=[]
  Closed=[]
  Path=[]

  if problem.isGoalState(Open[0]) is True:
      return State
  else:
       while Open:
                visit= Open.pop()
                Closed.append(visit)
                if State: 
                  Path.append(State.pop())

                if problem.isGoalState(visit) is True:
                    print Closed
                    return Path
                else:
                    Successors= problem.getSuccessors(visit)
                    for index in Successors:
                            it=iter(index)
                            data=it.next()

                            if data not in Closed :
                              Open.append(data)
                              State.append(it.next())
                            else:
                              print Path

Now if you will read my code under dfs you will see that open list contains all the points I visit and expanded.

The Path file contains the direction set for the pacman. The problem arises when I face the condition that both successors I get are unvisited, my pacman takes a path which leads to a dead end so it needs to backtrace. My Open does it and finds the solution but I am not able to find a way on how to provide the directions of backtracing in my path list. If you will go to http://inst.eecs.berkeley.edu/~cs188/sp09/projects/search/search.html and download the zip and paste my code in search.py under dfs search you will understand my problem.

Answer 1

Some hints:

• Each node you check should encapsulate the data of how you got there.
• DFS is like a stack; you start by pushing the start state. You pop the stack, and push back the nodes that can follow from the node you popped.
• Since you are ultimately trying to find a path, the node data must hold your location and the path you took to get there.