如何用算法来解决爱因斯坦在20世纪初出的这个谜语

偶们要把这个题目弄成新员工入职笔试题和上级题，呵呵。。。

今天该巨牛同事的工时记入研发工时，呵呵。。。

zhanghong

原帖由 zn519 于 2008-3-28 17:00 发表
同事无聊，信手拈来，几分钟思考后，写了段代码并输出了结果。以下是部分代码内容，俺没看懂的说

据说这一段是核心算法：

public class Einstein{

        public static void main(String[] args) {
                List hl = new LinkedList();
                for (int i = 0; i < 5; i++) {
                        hl.add(i);
                }
                List random = DFC(hl);
                List houseList = new LinkedList();
                List countryList = new LinkedList();
                List petList = new LinkedList();
                List drinkList = new LinkedList();
                List smokeList = new LinkedList();
                for (List o : random) {
                        List hList = new LinkedList();
                        List cList = new LinkedList();
                        List pList = new LinkedList();
                        List dList = new LinkedList();
                        List sList = new LinkedList();
                        for (Object oo : o) {
                                int i = (Integer) oo;
                                hList.add(House.values());
                                cList.add(Country.values());
                                pList.add(Pet.values());
                                dList.add(Drink.values());
                                sList.add(Smoke.values());
                        }
                        houseList.add(hList);
                        countryList.add(cList);
                        petList.add(pList);
                        drinkList.add(dList);
                        smokeList.add(sList);
                }
                // 第一趟，循环国家
                for (List c : countryList) {
                        // 9、挪威人住第一间房
                        if (c.get(0) != Country.norway)
                                continue;
                        // 第二趟，循环房子
                        for (List h : houseList) {
                                // 1、英国人住红房子
                                if (c.indexOf(Country.english) != h.indexOf(House.red))
                                        continue;
                                // 4、绿房子在白房子左边
                                if (h.indexOf(House.white) - h.indexOf(House.green) != 1)
                                        continue;
                                // 14、挪威人住蓝色房子隔壁
                                int p14 = c.indexOf(Country.norway) - h.indexOf(House.blue);
                                if (p14 != 1 && p14 != -1)
                                        continue;
                                // 第三趟，循环饮料
                                for (List d : drinkList) {
                                        // 3、丹麦人喝茶
                                        if (d.indexOf(Drink.tea) != c.indexOf(Country.danmark))
                                                continue;
                                        // 5、绿色房子喝咖啡
                                        if (d.indexOf(Drink.coffee) != h.indexOf(House.green))
                                                continue;
                                        // 8、中间房子喝牛奶
                                        if (d.indexOf(Drink.milk) != 2)
                                                continue;
                                        // 第四趟，循环烟
                                        for (List s : smokeList) {
                                                // 7、黄色房子主人抽Dunhill 香烟
                                                if (h.indexOf(House.yellow) != s.indexOf(Smoke.D))
                                                        continue;
                                                // 12、抽Blue Master的人喝啤酒
                                                if (d.indexOf(Drink.beer) != s.indexOf(Smoke.BM))
                                                        continue;
                                                // 13、德国人抽Prince香烟
                                                if (c.indexOf(Country.germen) != s.indexOf(Smoke.P))
                                                        continue;
                                                // 15、抽Blends香烟的人有一个喝水的邻居
                                                int p15 = d.indexOf(Drink.water) - s.indexOf(Smoke.B);
                                                if (p15 != 1 && p15 != -1)
                                                        continue;
                                                // 第五趟，循环宠物
                                                for (List p : petList) {
                                                        // 2、瑞典人养狗
                                                        if (p.indexOf(Pet.dog) != c.indexOf(Country.sweeden))
                                                                continue;
                                                        // 6、抽Pall Mall 香烟的人养鸟
                                                        if (p.indexOf(Pet.bird) != s.indexOf(Smoke.PM))
                                                                continue;
                                                        // 10、抽Blends香烟的人住在养猫的人隔壁
                                                        int p10 = p.indexOf(Pet.cat) - s.indexOf(Smoke.B);
                                                        if (p10 != 1 && p10 != -1)
                                                                continue;
                                                        // 11、养马的人住抽Dunhill 香烟的人隔壁
                                                        int p11 = p.indexOf(Pet.horse) - s.indexOf(Smoke.D);
                                                        if (p11 != 1 && p11 != -1)
                                                                continue;
                                                        System.out.println("答案：");
                                                        System.out.println("房间顺序："+h);
                                                        System.out.println("国家顺序："+c);
                                                        System.out.println("饮料顺序："+d);
                                                        System.out.println("香烟顺序："+s);
                                                        System.out.println("宠物顺序："+p);
                                                }
                                        }
                                }
                        }
                }

        }

        public static List DFC(List values) {
                List result = new LinkedList();
                if (values.size() == 1) {
                        List r = new LinkedList();
                        r.add(values.get(0));
                        result.add(r);
                } else {
                        for (int i = 0; i < values.size(); i++) {
                                List t = new LinkedList(values);
                                t.remove(i);
                                List tr = DFC(t);
                                for (List temp : tr) {
                                        List r = new LinkedList();
                                        r.add(values.get(i));
                                        r.addAll(temp);
                                        result.add(r);
                                }
                        }
                }
                return result;
        }

}





答案：
房间顺序：[yellow, blue, red, green, white]
国家顺序：[norway, danmark, english, germen, sweeden]
饮料顺序：[water, tea, milk, coffee, beer]
香烟顺序：[D, B, PM, P, BM]
宠物顺序：[cat, horse, bird, fish, dog]



代码不全，但核心算法已经有了，凑合着看吧

佩服

xiebinren

面试题目

sunyii

好棒~

takhsis

这个用电脑做很简单.至少brute-force就行.用人脑做也比较简单啊,从头走到尾都每一步都可直接得到,连假设都不需要的.起始的条件很明显.

共六个属性:NUM:号码. COLOR:颜色. NAT:国籍. DRINK:饮料. TAC:香烟. PET:宠物.

按照下列顺序走.
条件9->    NUM:1. COLOR:*.  NAT: 挪威. DRINK:*.     TAC:*.            PET:*.
条件14->  NUM:2. COLOR:蓝. NAT:*.      DRINK:*.     TAC:*.            PET:*.
条件4/1-> NUM:1. COLOR:黄. NAT:挪威.  DRINK:*.     TAC:*.            PET:*. (关键步骤)
条件7->    NUM:1. COLOR:黄  NAT:挪威.  DRINK:*.     TAC: Dunhill.   PET:*.
条件11->  NUM:2. COLOR:蓝. NAT:*.      DRINK:*.     TAC:*.            PET:马.

条件8->    NUM:3. COLOR:*.  NAT:*.      DRINK:牛奶. TAC:*.            PET:*.
条件4/5-> NUM:4. COLOR:绿. NAT:*.      DRINK:咖啡. TAC:*.            PET:*.
条件4->    NUM:5. COLOR:白. NAT:*.      DRINK:*.     TAC:*.            PET:*.
条件3->    NUM:3. COLOR:红. NAT:英国.  DRINK:牛奶. TAC:*.            PET:*.

条件3/12-> NUM:1. COLOR:黄. NAT:挪威. DRINK:水.    TAC: Dunhill.         PET: *.
条件15 ->   NUM:2. COLOR:蓝. NAT:*.     DRINK:*.     TAC: Blends.         PET: 马.
条件12->    NUM:5. COLOR:白. NAT:*.     DRINK:啤酒. TAC: Blue Master. PET:*.
条件3->      NUM:2. COLOR:蓝. NAT: 丹麦.DRINK:茶.    TAC: Blends.         PET: 马.  (2号全部到位)

条件13->    NUM:4. COLOR:绿. NAT:德国. DRINK:咖啡. TAC:Prince.          PET:*.
条件6->      NUM:3. COLOR:红. NAT:英国. DRINK:牛奶. TAC:Pall Mall.       PET:鸟. (3号全部到位)
条件10->    NUM:1. COLOR:黄. NAT:挪威. DRINK:水.    TACunhill.         PET: 猫. (1号全部到位)
条件2->      NUM:5. COLOR:白. NAT:瑞典. DRINK:啤酒. TAC:Blue Master. PET:狗. (5号全部到位)

到此为止,只有4号的PET为空.鱼是4号:
NUM:4. COLOR:绿. NAT:德国. DRINK:咖啡. TAC:Prince. PET:鱼.

爱因思坦不愿意出这种题目的.

sap-seal

綠色不一定緊挨著白色﹐只要在左邊即可