爱因斯坦-五色房子-三种解答（python-PyCharm版）

#计算用时:76.5892秒 #解决方案： #House 1 - Color: yellow黄, Nationality: norwegian挪威, Pet: cat猫, Drink: water开水, Smoke: 中华烟|顿|Dunhill #House 2 - Color: blue蓝, Nationality: dane丹麦, Pet: horse马, Drink: tea绿茶, Smoke: 利群烟|波|Blends #House 3 - Color: red红, Nationality: english英国, Pet: bird鸟, Drink: milk牛奶, Smoke: 红塔山|魔|Pall Mall #House 4 - Color: green绿, Nationality: german德国, Pet: fish鱼, Drink: coffee咖啡, Smoke: 三五牌|子|Prince #House 5 - Color: ivory白, Nationality: swede瑞典, Pet: dog狗, Drink: beer啤酒, Smoke: 小熊猫|领|BlueMaster #Process finished with exit code 0 import time # ~ num = 0 start = time.time() def solve_einstein_puzzle(): colors = ['red红', 'green绿', 'ivory白', 'yellow黄', 'blue蓝'] nationalities = ['english英国', 'swede瑞典', 'dane丹麦', 'norwegian挪威', 'german德国'] pets = ['dog狗', 'cat猫', 'bird鸟', 'horse马', 'fish鱼'] drinks = ['coffee咖啡', 'tea绿茶', 'milk牛奶', 'beer啤酒', 'water开水'] smokes = ['中华烟|顿|Dunhill', '红塔山|魔|Pall Mall', '利群烟|波|Blends', '三五牌|子|Prince', '小熊猫|领|BlueMaster'] def is_valid(houses): # 检查当前房子组合是否满足限制条件 for i in range(len(houses)): if houses[i]['nationality'] == 'english英国' and houses[i]['color'] != 'red红': return False #01 if houses[i]['nationality'] == 'swede瑞典' and houses[i]['pet'] != 'dog狗': return False #02 if houses[i]['nationality'] == 'dane丹麦' and houses[i]['drink'] != 'tea绿茶': return False #03 if houses[i]['smoke'] == '红塔山|魔|Pall Mall' and houses[i]['pet'] != 'bird鸟': return False #04 #if i == 0 and houses[i]['nationality'] != 'norwegian挪威': # return False # 10* if houses[i]['color'] == 'yellow黄' and houses[i]['smoke'] != '中华烟|顿|Dunhill': return False #05 if houses[i]['smoke'] == '小熊猫|领|BlueMaster' and houses[i]['drink'] != 'beer啤酒': return False #06 if houses[i]['nationality'] == 'german德国' and houses[i]['smoke'] != '三五牌|子|Prince': return False #07 #if i == 2 and houses[i]['drink'] != 'milk牛奶': # return False #08 if houses[i]['color'] == 'green绿' and houses[i]['drink'] != 'coffee咖啡': return False #09 if houses[i]['smoke'] == '利群烟|波|Blends': if i == 0 and houses[i + 1]['pet'] != 'cat猫': return False if i == 4 and houses[i - 1]['pet'] != 'cat猫': return False if i > 0 and houses[i - 1]['pet'] != 'cat猫' and houses[i + 1]['pet'] != 'cat猫': return False #12 if houses[i]['pet'] == 'horse马': if i == 0 and houses[i + 1]['smoke'] != '中华烟|顿|Dunhill': return False if i == 4 and houses[i - 1]['smoke'] != '中华烟|顿|Dunhill': return False if i > 0 and houses[i - 1]['smoke'] != '中华烟|顿|Dunhill' and houses[i + 1]['smoke'] != '中华烟|顿|Dunhill': return False #13 #if i == 1 and houses[i]['color'] != 'blue蓝': # return False #14 if houses[i]['smoke'] == '利群烟|波|Blends': if i == 0 and houses[i + 1]['drink'] != 'water开水': return False if i == 4 and houses[i - 1]['drink'] != 'water开水': return False if i > 0 and houses[i - 1]['drink'] != 'water开水' and houses[i + 1]['drink'] != 'water开水': return False #15 if houses[i]['color'] == 'ivory白': if i < 4 and houses[i + 1]['color'] != 'green绿': return False # 11 if houses[2]['drink'] != 'milk牛奶': return False #08 if houses[0]['nationality'] != 'norwegian挪威': return False # 10* if houses[1]['color'] != 'blue蓝': return False #14 return True def backtrack(houses, index): if index == 5: return houses for color in colors: if color in [h['color'] for h in houses]: continue houses[index]['color'] = color for nationality in nationalities: if nationality in [h['nationality'] for h in houses]: continue houses[index]['nationality'] = nationality for drink in drinks: if drink in [h['drink'] for h in houses]: continue houses[index]['drink'] = drink for smoke in smokes: if smoke in [h['smoke'] for h in houses]: continue houses[index]['smoke'] = smoke for pet in pets: if pet in [h['pet'] for h in houses]: continue houses[index]['pet'] = pet if is_valid(houses): result = backtrack(houses, index + 1) if result is not None: return result # ~ num += 1 # ~ print("总运行次数 %d" % num) exit() end = time.time() print("计算用时:%0.4f秒" % (end - start)) houses[index]['pet'] = None houses[index]['smoke'] = None houses[index]['drink'] = None houses[index]['nationality'] = None houses[index]['color'] = None return None # 初始化房子列表 houses = [{'color': None, 'nationality': None, 'pet': None, 'drink': None, 'smoke': None} for i in range(5)] result = backtrack(houses, 0) return result # 调用函数并输出结果 solution = solve_einstein_puzzle() if solution is not None: print('解决方案：') for i in range(5): print(f"House {i + 1} - Color: {solution[i]['color']}, Nationality: {solution[i]['nationality']}, Pet: {solution[i]['pet']}, Drink: {solution[i]['drink']}, Smoke: {solution[i]['smoke']}") else: print('无解')