让我们假设有一个七个人的家庭，例如，
["John", "James", "Jenna", "Joseph", "Jane", "Jacob", "Joanne"]
他们都为圣诞节礼物捐赠季节做好了准备。他们已经同意一些规则，以确保一切都能顺利进行：
- 每个人都必须送一个礼物。
- 每个人都必须收到一份礼物。
- 没有人可以给自己礼物。
- 没有人可以给他的配偶礼物。（简和约翰是配偶）
- 没有人可以给他去年给出的同一个人。（去年，约翰给了詹姆斯，詹姆斯给了珍娜，珍娜给了约瑟夫，约瑟夫给了珍妮，珍妮给了雅各布，雅各布，雅各给了乔安妮，乔安妮给了约翰） ）
- 最后，没有两个人可以互相送礼物。例如，如果约翰奉献给珍娜，珍娜可能不会回馈约翰。
由于规则如此复杂，他们很难弄清楚谁能在仍遵守这些规则的同时给谁捐赠。因此，他们雇用了我编写一个计划，该程序将展示人们彼此提供的所有可能的法律方式。
我可以用哪种算法优雅地解决这个问题？
我将使用简单的回溯算法。使用Python发电机函数：
def calc_gifts(names, blacklist, gifts={}):
if len(names) > 0:
name, rest = names[0], names[1:]
for other in names + list(gifts):
if (other != name and
other not in blacklist[name] and
(other not in gifts or gifts[other] != name) and
other not in gifts.values()):
gifts_new = dict(gifts.items() + [(name, other)])
for solution in calc_gifts(rest, blacklist, gifts_new):
yield solution
else:
yield gifts
现在，我们设置了名称和黑名单，并让生成器生成解决方案：
all_names = ["john", "james", "jenna", "joseph", "jane", "jacob", "joanne"]
blacklist = {"john": ["james", "jane"],
"james": ["jenna"],
"jenna": ["joseph"],
"joseph": ["jane"],
"jane": ["jacob", "john"],
"jacob": ["joanne"],
"joanne": ["john"]}
generator = calc_gifts(all_names, blacklist)
solution = next(generator)
solution然后是礼品奖和 - 捕获者的dict，例如{'joanne': 'joseph', 'james': 'john', 'jane': 'joanne', 'joseph': 'jacob', 'jacob': 'jane', 'john': 'jenna', 'jenna': 'james'}。
对于第一个解决方案，即使用next(generator)，calc_gifts仅调用10次；对于所有224个解决方案，例如使用list(generator)大约调用。1000次。
如果您从7x7网格开始，每个人都有一个行和列在列中。
最初，将所有组合标记为允许，然后开始删除由您的约束3、4和5明确禁止的组合。此时离开了。这将是您的首发位置。
现在您必须开始做出决定，每个决定都会影响您剩下的可能性。某些决定可能是错误的，导致并非所有人最终都得到礼物。在这种情况下，您应该取回该决定，然后尝试另一个决定（提示：为此使用递归）。
如果您以结构化的方式尝试所有可能性，则必须找到所有解决方案。
现在，让他们的钱值得：）