Найдите жизнеспособную комбинацию из списка предпочтений

У меня есть объект, который выглядит так:

a - ['A', 'B', 'C']
b - ['A', 'B', 'C']
c - ['A', 'B', 'C', 'D']
d - ['A', 'B', 'C', 'D']

Каждый из ключей имеет ряд доступных опций, как указано в списке (например, a может выбирать между A, B, C и т. д.). Я хочу найти сочетание пар, которое удовлетворит всех. Это должно быть:

#   Chosen  Remaining          Available Options
------------------------------------------
a - B       - ['A', 'B', 'C'] - ['A', 'B', 'C']
b - A       - ['A', 'C']      - ['A', 'B', 'C']
c - D       - ['C', 'D']      - ['A', 'B', 'C', 'D']
d - C       - ['C']           - ['A', 'B', 'C', 'D']

Итак, в приведенном выше примере a выбрал элемент B, уменьшив пул доступных вариантов для остальных участников. b затем выбрал элемент A и так далее.

Я делаю это, просматривая всех участников в зависимости от того, насколько велик пул их доступных вариантов выбора, идея состоит в том, что если у меня есть участник, который хочет только один элемент, тогда нет другого выбора, кроме как дать ему этот элемент, удалив его из бассейн.

import random

team_choices = {'a': ['A', 'B', 'C'],
                'b': ['A', 'B', 'C'],
                'c': ['A', 'B', 'C', 'D'],
                'd': ['A', 'B', 'C', 'D']}
teams_already_created = []
for team_b in sorted(team_choices, key=team_choices.__getitem__, reverse=False):
    available_opponents = [opponent for opponent in team_choices[team_b] if opponent not in teams_already_created]
    chosen_opponent = random.choice(available_opponents)
    teams_already_created.append(chosen_opponent)

Но то, как я это делаю, не всегда будет работать хорошо, поскольку нет гарантии, что в какой-то момент он сделает выбор, который позже задушит другого игрока, не оставив ему доступных вариантов. И если chosen_opponent пуст, то, очевидно, это не удастся.

Есть ли лучший способ сделать это, который будет работать каждый раз?