After trying to get this program to run faster and use less memory, it is unclear to me what more can be done to have this code complete the challenge in a timely fashion.

"""\
Every Christmas in my family, each of us gives a present to only one other
person. To organize who should offer a gift to whom (I call it the chain of
presents), we introduced a few rules:

 - There should be a single chain where every person in the family is present,
 - Couples should not give to one another,
 - Every person should give a gift to a different person than they had in
   previous years

So the problem would be to find and list the longest list of chains of
presents. For example in a family {a,b,c,d} with couples=({a,b},{c,d}):
[[a,c,b,d],[a,d,b,c]].

You are given a set of family member names and a list of couples in this
family. Find the maximum number of chains with all family members. Gift chains
should be represented as a list of names where i-th gives a present to i+1-th
and the last person in the list to the first.

Input:        Names of family members as a set of strings. Couple list as a
              tuple of sets with two strings in each.
Output:       The longest list of gift chains as a list/tuple of lists/tuples
              with strings.
Precondition: len(couples) <= 7"""

from operator import itemgetter
from pprint import pprint

Z = frozenset

TABLE = {(Z({'Hollie', 'Gary', 'Jeanette'}),
          Z({Z({'Gary', 'Jeanette'})})): 0,
         (Z({'Javier', 'Rachel', 'Curtis', 'Lee'}),
          Z({Z({'Curtis', 'Lee'}), Z({'Javier', 'Rachel'})})): 2,
         (Z({'Mary', 'Selena', 'Phyllis', 'Philip', 'Eric', 'Sondra'}),
          Z({Z({'Mary', 'Eric'}), Z({'Philip', 'Sondra'})})): 4,
         (Z({'Eugene', 'Delores', 'Delia', 'Ricardo', 'Ella', 'Kurt'}),
          Z({Z({'Ella', 'Eugene'}), Z({'Delores', 'Kurt'}),
             Z({'Delia', 'Ricardo'})})): 4,
         (Z({'Nelson', 'Kaitlin', 'Amelia', 'Jack'}),
          Z({Z({'Nelson', 'Amelia'}), Z({'Kaitlin', 'Jack'})})): 2,
         (Z({'Eugenia', 'Alex', 'Monique', 'Kitty', 'Robert', 'Tamika', 'Rene',
             'Tim', 'Maggie', 'Joseph'}),
          Z({Z({'Tim', 'Tamika'}), Z({'Robert', 'Kitty'}),
             Z({'Eugenia', 'Alex'}), Z({'Monique', 'Rene'}),
             Z({'Maggie', 'Joseph'})})): 8,
         (Z({'Melisa', 'Annmarie', 'Dee', 'Rafael', 'Gerald'}),
          Z({Z({'Melisa', 'Gerald'}), Z({'Annmarie', 'Rafael'})})): 2,
         (Z({'Lula', 'Bill', 'Irene', 'Vincent', 'Dorothea', 'Paulette',
             'Virginia'}),
          Z()): 6,
         (Z({'Tabitha', 'Esperanza', 'Delores', 'Carl', 'Erin', 'Samuel',
             'Fred', 'Erica', 'Amber', 'Dixie'}),
          Z({Z({'Fred', 'Delores'}), Z({'Erica', 'Carl'})})): 7,
         (Z({'Herminia', 'Louis', 'David', 'Sondra', 'Herbert', 'Jane',
             'Jeannie', 'Alexandria', 'Theodore', 'Meghan', 'Nettie',
             'Eleanor', 'Autumn', 'Jeffery', 'Fay', 'June', 'Lynnette'}),
          Z({Z({'Theodore', 'Meghan'}), Z({'David', 'Nettie'}),
             Z({'Louis', 'Autumn'}), Z({'Herbert', 'Eleanor'}),
             Z({'Fay', 'Jeffery'})})): 14,
         (Z({'Fred', 'Yolanda', 'Doreen'}),
          Z({Z({'Fred', 'Doreen'})})): 0,
         (Z({'Jacklyn', 'Maurice', 'Lela', 'Stella', 'Winnie', 'Barbra',
             'Lavonne', 'Estela', 'Gordon'}),
          Z({Z({'Maurice', 'Lela'})})): 7,
         (Z({'Russell', 'Maryanne', 'Benjamin', 'Matthew', 'Loraine', 'Penny',
             'Todd', 'Jenifer', 'Leah'}),
          Z({Z({'Jenifer', 'Todd'}), Z({'Benjamin', 'Loraine'}),
             Z({'Leah', 'Matthew'})})): 6,
         (Z({'Kelly', 'Allison', 'Bobbie', 'Curtis', 'Petra', 'Robin'}),
          Z({Z({'Robin', 'Kelly'}), Z({'Curtis', 'Allison'})})): 4}

def main():
    "Test the find_chains function with several cases to see if it breaks."
    assert checker(find_chains,
                   {'Gary', 'Jeanette', 'Hollie'},
                   ({'Gary', 'Jeanette'},),
                   0), "Three of us"
    assert checker(find_chains,
                   {'Curtis', 'Lee', 'Rachel', 'Javier'},
                   ({'Rachel', 'Javier'}, {'Curtis', 'Lee'}),
                   2), "Pairs"
    assert checker(find_chains,
                   {'Philip', 'Sondra', 'Mary', 'Selena', 'Eric', 'Phyllis'},
                   ({'Philip', 'Sondra'}, {'Eric', 'Mary'}),
                   4), "Pairs and Singles"
    for (family, couples), total in sorted(TABLE.items(), key=itemgetter(1)):
        print('total =', total)
        assert checker(find_chains, set(family), couples, total), 'Full Test'

def checker(function, family, couples, total):
    "Check the function with family and couples to see if it works correctly."
    user_result = function(family.copy(), tuple(c.copy() for c in couples))
    pprint(user_result)
    if (not isinstance(user_result, (list, tuple)) or
        any(not isinstance(chain, (list, tuple)) for chain in user_result)):
        return False
    if len(user_result) < total:
        return False
    gifted = set()
    for chain in user_result:
        if set(chain) != family or len(chain) != len(family):
            return False
        for f, s in zip(chain, chain[1:] + [chain[0]]):
            if {f, s} in couples:
                return False
            if (f, s) in gifted:
                return False
            gifted.add((f, s))
    return True

################################################################################

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:

    __slots__ = 'family', 'couples', 'target', 'options', 'state'

    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:

    __slots__ = 'chain', 'options'

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

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

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

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

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

    @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,)

    @property
    def score(self):
        return len(self.chain)

    @property
    def children(self):
        for chain in self.combinations_with_refinement(min(self.options)):
            yield type(self)(self.chain + (chain,), self.options)

    def combinations_with_refinement(self, primer):
        options = self.options
        for chain in self.chain:
            options = {start: options[start] - {stop} for start, stop in
                       pairwise(chain + (chain[0],))}
        yield from self._cwr((primer,), primer, primer, 1, len(options),
                             options)

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

if __name__ == '__main__':
    main()