The code below works until the system runs out of memory. My guess is that a state's score is not drawing good states quickly enough to the top of the heap The __lt__ method is inversed so that higher scores are favored. States get a higher score for longer chains but are penalized for the most common shared person that people can give to. The __eq__ and __hash__ methods are designed to avoid duplicate states.

Can anyone recommend a better way of calculating the score for a state?

from collections import Counter
from heapq import heappop, heappush
from itertools import chain, tee

def find_chains(family, couples):
    "Return the longest list of gift chains as a list of lists."
    target = TABLE[Z(family), Z(map(Z, couples))]
    if not target:
        return ()
    return tuple(map(list, Machine(family, couples, target).search()))

def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

class Machine:

    def __init__(self, family, couples, target):
        self.family = family
        self.couples = couples
        self.target = target
        self.options = {name: family - {name} for name in family}
        for a, b in couples:
            self.options[a].remove(b)
            self.options[b].remove(a)
        self.state = State((), self.options)

    def search(self):
        heap, skip = [self.state], {self.state}
        while heap:
            state = heappop(heap)
            for child in state.children:
                if len(child.chain) == self.target:
                    return child.chain
                if child not in skip:
                    skip.add(child)
                    heappush(heap, child)
        return ()

class State:

    def __init__(self, chain, options):
        self.chain = chain
        self.options = options

    def __lt__(self, other):
        return self.score > other.score

    @property
    def score(self):
        score = len(self.chain)
        score -= Counter(chain(*self.options.values())).most_common(1)[0][1]
        return score

    def __eq__(self, other):
        return set(self.chain) == set(other.chain)

    def __hash__(self):
        return hash(frozenset(self.chain))

    @property
    def children(self):
        for chain in self.combinations_with_refinement(min(self.options)):
            yield type(self)(self.chain + (chain,), {start: self.options
            [start] - {stop} for start, stop in pairwise(chain + (chain[0],))})

    def combinations_with_refinement(self, primer):
        yield from self._cwr((primer,), primer, primer, 1, len(self.options))

    def _cwr(self, chain, head, tail, size, goal):
        size += 1
        if size < goal:
            for option in self.options[tail]:
                if option not in chain:
                    yield from self._cwr(chain + (option,),
                                         head, option, size, goal)
        else:
            for option in self.options[tail]:
                if option not in chain and head in self.options[option]:
                    yield chain + (option,)