class SearchNode:

def __init__(self, action, state, parent):

self.state = state

self.action = action

self.parent = parent

def path(self):

if self.parent == None:

return [(self.action, self.state)]

else:

return self.parent.path() + [(self.action, self.state)]

def inPath(self, s):

if s == self.state:

return True

elif self.parent == None:

return False

else:

return self.parent.inPath(s)

def breadthFirstSearch(initialState, goalTest, actions, successor):

agenda = Queue()

if goalTest(initialState):

return [(None, initialState)]

agenda.push(SearchNode(None, initialState, None))

while not agenda.isEmpty():

parent = agenda.pop()

newChildStates = []

for a in actions(parent.state):

newS = successor(parent.state, a)

newN = SearchNode(a, newS, parent)

if goalTest(newS):

return newN.path()

elif newS in newChildStates:

pass

elif parent.inPath(newS):

pass

else:

newChildStates.append(newS)

agenda.push(newN)

return None