爱因斯坦的思考题

[likebeta]

传说是爱因斯坦提出来的逻辑思考题，据说只有2%的人能解出。题目是这样的，有五个不同颜色的房间排成一排，每个房间里分别住着一个不同国籍的人，每个人都喝一种特定品牌的饮料，抽一种特定品牌的烟，养一种宠物。每种事务都是不重复的。问题是谁在养鱼？ 以下是给出的15条线索。

1. 英国人住在红色的房子里；
2. 瑞典人养狗作为宠物；
3. 丹麦人喝茶；
4. 绿房子紧挨着白房子，在白房子的左边；
5. 绿房子的主人喝咖啡；
6. 抽Pall Mall牌香烟的人养鸟；
7. 黄色房子里的人抽Dunhill牌香烟；
8. 住在中间那个房子里的人喝牛奶；
9. 挪威人住在第一个房子里面；
10. 抽Blends牌香烟的人和养猫的人相邻；
11. 养马的人和抽Dunhill牌香烟的人相邻；
12. 抽BlueMaster牌香烟的人喝啤酒；
13. 德国人抽Prince牌香烟；
14. 挪威人和住在蓝房子的人相邻；
15. 抽Blends牌香烟的人和喝矿泉水的人相邻。

分析

这个问题说难也不难，问题就在有太多的组合，人很难同时处理这么多种线索，当然找一张纸和一支笔慢慢的推理，只要耐心并且肯花时间还是可以做出来的。但问题的关键是： 难道只有一种结果吗？

根据排列组合可以算出来大概有199065600中组合，也就是差不多2亿种情况需要考虑。人脑如果想验证所有的情况， 我觉得会导致脑残。那我们用计算机来试试吧。

数据模型

5种颜色的房子， 5种国籍， 5种饮料， 5中宠物和5种牌子的香烟。一个人只能拥有每种事物中的一个，那么可以定义出一个Person的概率。

class Person(object):
    def __init__(self, house=None, nation=None, drink=None, pet=None, cigaret=None):
        self.house = house
        self.nation = nation
        self.drink = drink
        self.pet = pet
        self.cigaret = cigaret

对于每种拥有的事物的类型进行枚举， 因为python中没有枚举， 可以用类来替代，比如房子：

class House(object):
    yellow = 1
    blue = 2
    red = 3
    green = 4
    white = 5

线索模型

通过分析可以把线索归为3大类：个人属性绑定关系，邻居间属性关联关系，其他

个人属性绑定关系

线索 1,2,3,5,6,7,12,13 都属于这一类。 我们可以定义出一个四元组数据结构[attr1, value1, attr2, value2]用来过滤不符合的条件。比如第1条线索可以表示为['house', House.red, 'nation', Nation.UK]， 待选组合必须同时满足个人属性绑定条件。

邻居间属性关联关系

线索 10,11,14,15 都属于这一类。我们也可以定义出一个四元组来表示邻居间的绑定关系[attr, value, relation_attr, relation_value]。比如第10条线索可以表示为['cigaret', Cigaret.Blends, 'pet', Pet.cat]，待选组合必须满足这种邻居间属性关联限制。

其他

线索 4,8,9 都是比较具体的要求， 不好归类。我们都可以在生成候选组合的时候直接应用这些线索。

实现

#!/usr/bin/env python
# -*- coding=utf-8 -*-

# Author: likebeta <ixxoo.me@gmail.com>
# Create: 2016-08-24


class House(object):
    yellow = 1
    blue = 2
    red = 3
    green = 4
    white = 5

    @classmethod
    def desc(cls, house):
        return {
            cls.yellow: u'黄色',
            cls.blue: u'蓝色',
            cls.red: u'红色',
            cls.green: u'绿色',
            cls.white: u'白色',
        }[house]


class Nation(object):
    Norway = 1
    Denmark = 2
    UK = 3
    Germany = 4
    Sweden = 5

    @classmethod
    def desc(cls, nation):
        return {
            cls.Norway: u'挪威',
            cls.Denmark: u'丹麦',
            cls.UK: u'英国',
            cls.Germany: u'德国',
            cls.Sweden: u'瑞典',
        }[nation]


class Drink(object):
    water = 1
    tea = 2
    milk = 3
    coffee = 4
    beer = 5

    @classmethod
    def desc(cls, drink):
        return {
            cls.water: u'水',
            cls.tea: u'茶',
            cls.milk: u'牛奶',
            cls.coffee: u'咖啡',
            cls.beer: u'啤酒',
        }[drink]


class Pet(object):
    cat = 1
    horse = 2
    bird = 3
    fish = 4
    dog = 5

    @classmethod
    def desc(cls, pet):
        return {
            cls.cat: u'猫',
            cls.horse: u'马',
            cls.bird: u'鸟',
            cls.fish: u'鱼',
            cls.dog: u'狗',
        }[pet]


class Cigaret(object):
    Dunhill = 1
    Blends = 2
    PallMall = 3
    Prince = 4
    BlueMaster = 5

    @classmethod
    def desc(cls, cigaret):
        return {
            cls.Dunhill: u'Dunhill',
            cls.Blends: u'Blends',
            cls.PallMall: u'PallMall',
            cls.Prince: u'Prince',
            cls.BlueMaster: u'BlueMaster',
        }[cigaret]


class Person(object):
    def __init__(self, house=None, nation=None, drink=None, pet=None, cigaret=None):
        self.house = house
        self.nation = nation
        self.drink = drink
        self.pet = pet
        self.cigaret = cigaret

    def desc(self):
        return u' '.join([House.desc(self.house), Nation.desc(self.nation),
                          Drink.desc(self.drink), Pet.desc(self.pet),
                          Cigaret.desc(self.cigaret)])


class Algorithm(object):
    item_count = 5
    #1,2,3,5,6,7,12,13
    bind_rule_list = [
        ['house', House.red, 'nation', Nation.UK],
        ['nation', Nation.Sweden, 'pet', Pet.dog],
        ['nation', Nation.Denmark, 'drink', Drink.tea],
        ['house', House.green, 'drink', Drink.coffee],
        ['cigaret', Cigaret.PallMall, 'pet', Pet.bird],
        ['house', House.yellow, 'cigaret', Cigaret.Dunhill],
        ['cigaret', Cigaret.BlueMaster, 'drink', Drink.beer],
        ['nation', Nation.Germany, 'cigaret', Cigaret.Prince],
    ]

    #10,11,14,15
    relation_rule_list = [
        ['cigaret', Cigaret.Blends, 'pet', Pet.cat],
        ['pet', Pet.horse, 'cigaret', Cigaret.Dunhill],
        ['nation', Nation.Norway, 'house', House.blue],
        ['cigaret', Cigaret.Blends, 'drink', Drink.water],
    ]

    def enum_house(self, person_list):
        if len(person_list) == self.item_count:
            person_list[0].nation = Nation.Norway  # 9
            self.enum_nation(person_list, 1)
            return

        for color in (House.yellow, House.blue, House.red, House.green):
            if not self.is_color_used(person_list, color):
                person_list.append(Person(house=color))
                if color == House.green:  # 4
                    person_list.append(Person(house=House.white))
                self.enum_house(person_list)
                if color == House.green:  # 4
                    person_list.pop()
                person_list.pop()

    def is_color_used(self, person_list, color):
        for one in person_list:
            if one.house == color:
                return True
        return False

    def enum_nation(self, person_list, index):
        if index == self.item_count:
            self.enum_drink(person_list, 0)
            return

        for nation in (Nation.Denmark, Nation.UK, Nation.Germany, Nation.Sweden):
            if not self.is_nation_used(person_list, index, nation):
                person_list[index].nation = nation
                self.enum_nation(person_list, index + 1)

    def is_nation_used(self, person_list, index, nation):
        for i in range(index):
            if person_list[i].nation == nation:
                return True
        return False

    def enum_drink(self, person_list, index):
        if index == self.item_count:
            self.enum_pet(person_list, 0)
            return

        if index == 2:  # 8
            person_list[index].drink = Drink.milk
            self.enum_drink(person_list, index + 1)
        else:
            for drink in (Drink.water, Drink.tea, Drink.coffee, Drink.beer):
                if not self.is_drink_used(person_list, index, drink):
                    person_list[index].drink = drink
                    self.enum_drink(person_list, index + 1)

    def is_drink_used(self, person_list, index, drink):
        for i in range(index):
            if person_list[i].drink == drink:
                return True
        return False

    def enum_pet(self, person_list, index):
        if index == self.item_count:
            self.enum_cigaret(person_list, 0)
            return

        for pet in (Pet.cat, Pet.horse, Pet.bird, Pet.fish, Pet.dog):
            if not self.is_pet_used(person_list, index, pet):
                person_list[index].pet = pet
                self.enum_pet(person_list, index + 1)

    def is_pet_used(self, person_list, index, pet):
        for i in range(index):
            if person_list[i].pet == pet:
                return True
        return False

    def enum_cigaret(self, person_list, index):
        if index == self.item_count:
            if self.check_bind_rule(person_list) and self.check_relation_rule(person_list):
                self.dump_rc_result(person_list)
                self.print_result(person_list)
        else:
            for cigaret in (Cigaret.Dunhill, Cigaret.Blends, Cigaret.PallMall, Cigaret.Prince, Cigaret.BlueMaster):
                if not self.is_cigaret_used(person_list, index, cigaret):
                    person_list[index].cigaret = cigaret
                    self.enum_cigaret(person_list, index + 1)

    def is_cigaret_used(self, person_list, index, cigaret):
        for i in range(index):
            if person_list[i].cigaret == cigaret:
                return True
        return False

    def check_bind_rule(self, person_list):
        for person in person_list:
            for rule in self.bind_rule_list:
                if getattr(person, rule[0], None) == rule[1]:
                    if getattr(person, rule[2], None) != rule[3]:
                        return False
        return True

    def check_relation_rule(self, person_list):
        for i, person in enumerate(person_list):
            for rule in self.relation_rule_list:
                if getattr(person, rule[0], None) == rule[1]:
                    if i == 0:
                        if getattr(person_list[1], rule[2], None) != rule[3]:
                            return False
                    elif i == self.item_count - 1:
                        if getattr(person_list[-2], rule[2], None) != rule[3]:
                            return False
                    else:
                        if getattr(person_list[i - 1], rule[2], None) != rule[3] and \
                                        getattr(person_list[i + 1], rule[2], None) != rule[3]:
                            return False
        return True

    def print_result(self, person_list):
        for person in person_list:
            line = person.desc()
            print line

    def dump_rc_result(self, person_list):
        _list = []
        for person in person_list:
            _list.append([person.house, person.nation, person.drink, person.pet, person.cigaret])
        print _list


if __name__ == '__main__':
    import sys
    import time

    alg = Algorithm()
    start = time.clock()
    alg.enum_house([])
    sys.stderr.write(str(time.clock() - start) + '\n')

运行下看看：

[[1, 1, 1, 1, 1], [2, 2, 2, 2, 2], [3, 3, 3, 3, 3], [4, 4, 4, 4, 4], [5, 5, 5, 5, 5]]
黄色 挪威 水 猫 Dunhill
蓝色 丹麦 茶 马 Blends
红色 英国 牛奶 鸟 PallMall
绿色 德国 咖啡 鱼 Prince
白色 瑞典 啤酒 狗 BlueMaster

好吧，有且只有一种组合。