State tree (Python recipe) by Glenn Hutchings

ActiveState Code (http://code.activestate.com/recipes/578159/)

"""
A 'state tree' is (as its name implies) an object that represents a tree of
states.  The tree is built by having an initial state (the 'root') and a
rule whereby child states can be reached from a parent state.

State trees are useful, for example, in solving puzzles where there are a
fixed set of moves from any given position, and a goal position which is
the solution.  A couple of example puzzles are given below.
"""

from collections import deque


class StateTree(object):
    """
    Representation of a tree of states.

    States must be hashable (i.e., usable as dictionary keys---for example,
    tuples).  The initial(), reachable() and endcondtion() methods must be
    subclassed.  After that, the findpath() method will return a list of
    states from the initial to an end state.
    """

    def initial(self):
        "Return the initial state."
        raise NotImplementedError

    def reachable(self, state):
        "Yield states reachable from a given state."
        raise NotImplementedError

    def endcondition(self, state):
        "Return whether state satisfies the end condition."
        raise NotImplementedError

    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


class BottlePuzzle(StateTree):
    """
    There are three bottles, with capacities of 3, 5 and 8 litres.  You can
    pour the contents of one bottle into another until it's empty or the
    other is full.  How do you measure out 4 litres?
    """

    # Bottle sizes.
    sizes = (3, 5, 8)

    # Possible pourings (from -> to).
    pourings = ((0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1))

    def initial(self):
        return (0, 0, 8)

    def reachable(self, state):
        for a, b in self.pourings:
            bottles = list(state)

            # Get the amount poured from bottle A to bottle B.
            poured = min(self.sizes[b] - bottles[b], bottles[a])

            # If some was poured, yield the new state.
            if poured > 0:
                bottles[a] -= poured
                bottles[b] += poured
                yield tuple(bottles)

    def endcondition(self, state):
        return 4 in state


class FrogsAndToads(StateTree):
    """
    The classic frogs-and-toads puzzle.  An equal number of frogs and toads
    face each other on a log, with a gap between them, and need to swap
    places.  Toads only move right, frogs only move left.  A thing can move
    into the gap, or jump over a different thing into the gap.  How do they
    do it?
    """

    def initial(self):
        return ('T', 'T', 'T', ' ', 'F', 'F', 'F')

    def reachable(self, state):
        for thing, move in (('T', 1), ('T', 2), ('F', -1), ('F', -2)):
            pos = list(state)

            # Find where the empty space is.
            space = pos.index(' ')

            # Find start position of the thing to move.
            start = space - move

            # If start position is out of bounds, or not of the right type,
            # disallow it.
            if not 0 <= start < len(pos) or pos[start] != thing:
                continue

            # If it's a jump, and the jumped thing isn't a different kind,
            # disallow it.
            if abs(move) == 2 and pos[(space + start) / 2] == thing:
                continue

            # Do the move and yield it.
            pos[start], pos[space] = pos[space], pos[start]
            yield tuple(pos)

    def endcondition(self, state):
        return state == ('F', 'F', 'F', ' ', 'T', 'T', 'T')

if __name__ == "__main__":
    for puzzle in FrogsAndToads, BottlePuzzle:
        print
        print puzzle.__name__
        print
        for state in puzzle().findpath():
            print "   ", state