def findpath(self):
        "Find and return shortest path from initial to end state."

        # Get the initial state.
        state = self.initial()

        # Mapping of state to its parent, or None if initial.
        parentmap = {state: None}

        # Queue of states to examine.
        queue = deque([state])

        # Process each state in the queue.
        while len(queue) > 0:
            state = queue.popleft()

            # Examine each new reachable state.
            for child in self.reachable(state):
                if child not in parentmap:
                    parentmap[child] = state
                    queue.append(child)

            # If this state satisfies the end condition, return it.
            if self.endcondition(state):
                states = [state]
                while parentmap[state] is not None:
                    state = parentmap[state]
                    states.insert(0, state)

                return states
Find and return shortest path from initial to end state.
recipes/Python/578159_State_tree_/recipe-578159.py