题目是这样的, 有五个不同颜色的房间排成一排, 每个房间里分别住着一个不同国籍的人, 每个人都喝一种特定品牌的饮料, 抽一种特定品牌的烟, 养一种宠物没有任意两个人的任意属性值是相同的问: 是谁在养鱼? 下面是给出的 15 条线索
英国人住在红色的房子里;
瑞典人养狗作为宠物;
丹麦人喝茶;
绿房子紧挨着白房子, 在白房子的左边;
绿房子的主人喝咖啡;
抽 Pall Mall 牌香烟的人养鸟;
黄色房子里的人抽 Dunhill 牌香烟;
住在中间那个房子里的人喝牛奶;
挪威人住在第一个房子里面;
抽 Blends 牌香烟的人和养猫的人相邻;
养马的人和抽 Dunhill 牌香烟的人相邻;
抽 BlueMaster 牌香烟的人喝啤酒;
德国人抽 Prince 牌香烟;
挪威人和住在蓝房子的人相邻;
抽 Blends 牌香烟的人和喝矿泉水的人相邻
求解思路: 多维穷举遍历每个属性值组成的人, 并用条件中的个体条件 (条件中只包含了一个人) 来筛选, 将其加入对应房子的候选人列表中然后对 5 个房子的候选人列表进行多重遍历, 并用事关两个人的条件 (比如条件 1011) 进行筛选, 而且选中的 5 个人的属性值不能重复, 最后输出正确答案代码如下:
- import java.util.Vector;
- public class Einstein {
- static class Person {
- final COLOR color;
- final NATION nation;
- final DRINK drink;
- final PET pet;
- final CIGARETTE cigarette;
- final int index; // 在几号房子
- public Person(COLOR color, NATION nation, DRINK drink, PET pet, CIGARETTE cigarette, int index) {
- this.color = color;
- this.nation = nation;
- this.drink = drink;
- this.pet = pet;
- this.cigarette = cigarette;
- this.index = index;
- }@Override public String toString() {
- return "Person{" + "color=" + color + ", nation=" + nation + ", drink=" + drink + ", pet=" + pet + ", cigarette=" + cigarette + ", index=" + index + '}';
- }
- }
- enum COLOR {
- Yellow,
- Blue,
- Red,
- Green,
- White
- }
- enum NATION {
- Norway,
- Denmark,
- England,
- Germany,
- Sweden
- }
- enum DRINK {
- Water,
- Tea,
- Milk,
- Coffee,
- Beer
- }
- enum PET {
- Cat,
- Horse,
- Bird,
- Fish,
- Dog
- }
- enum CIGARETTE {
- Dunhill,
- Blends,
- PallMall,
- Prince,
- BlueMaster
- }
- boolean test1(final Person person) {
- return (person.color == COLOR.Red && person.nation == NATION.England) || (person.color != COLOR.Red && person.nation != NATION.England);
- }
- boolean test2(final Person person) {
- return (person.nation == NATION.Sweden && person.pet == PET.Dog) || (person.nation != NATION.Sweden && person.pet != PET.Dog);
- }
- boolean test3(final Person person) {
- return (person.nation == NATION.Denmark && person.drink == DRINK.Tea) || (person.nation != NATION.Denmark && person.drink != DRINK.Tea);
- }
- boolean test5(final Person person) {
- return (person.color == COLOR.Green && person.drink == DRINK.Coffee) || (person.color != COLOR.Green && person.drink != DRINK.Coffee);
- }
- boolean test6(final Person person) {
- return (person.cigarette == CIGARETTE.PallMall && person.pet == PET.Bird) || (person.cigarette != CIGARETTE.PallMall && person.pet != PET.Bird);
- }
- boolean test7(final Person person) {
- return (person.color == COLOR.Yellow && person.cigarette == CIGARETTE.Dunhill) || (person.color != COLOR.Yellow && person.cigarette != CIGARETTE.Dunhill);
- }
- boolean test8(final Person person) {
- return (person.index == 2 && person.drink == DRINK.Milk) || (person.index != 2 && person.drink != DRINK.Milk);
- }
- boolean test9(final Person person) {
- return (person.index == 0 && person.nation == NATION.Norway) || (person.index != 0 && person.nation != NATION.Norway);
- }
- boolean test12(final Person person) {
- return (person.cigarette == CIGARETTE.BlueMaster && person.drink == DRINK.Beer) || (person.cigarette != CIGARETTE.BlueMaster && person.drink != DRINK.Beer);
- }
- boolean test13(final Person person) {
- return (person.nation == NATION.Germany && person.cigarette == CIGARETTE.Prince) || (person.nation != NATION.Germany && person.cigarette != CIGARETTE.Prince);
- }
- boolean test14(final Person person) {
- return (person.color == COLOR.Blue && person.index == 1) || (person.color != COLOR.Blue && person.index != 1);
- }
- private Vector < Person > house0 = new Vector < >();
- private Vector < Person > house1 = new Vector < >();
- private Vector < Person > house2 = new Vector < >();
- private Vector < Person > house3 = new Vector < >();
- private Vector < Person > house4 = new Vector < >();
- public void search() {
- // 先构造满足个体条件的人, 然后加入不同的房子里, 再对房子里面的人进行循环
- for (COLOR color: COLOR.values()) {
- for (NATION nation: NATION.values()) {
- for (DRINK drink: DRINK.values()) {
- for (PET pet: PET.values()) {
- for (CIGARETTE cigarette: CIGARETTE.values()) {
- for (int index = 0; index < 5; index++) {
- final Person person = new Person(color, nation, drink, pet, cigarette, index);
- // 如果这个人满足个体条件, 则加入对应的房子
- if (test1(person) && test2(person) && test3(person) && test5(person) && test6(person) && test7(person) && test8(person) && test9(person) && test12(person) && test13(person) && test14(person)) {
- switch (person.index) {
- case 0:
- house0.add(person);
- break;
- case 1:
- house1.add(person);
- break;
- case 2:
- house2.add(person);
- break;
- case 3:
- house3.add(person);
- break;
- case 4:
- house4.add(person);
- break;
- }
- }
- }
- }
- }
- }
- }
- }
- // 对 5 个房子里面的人进行循环
- for (Person person0:
- house0) {
- for (Person person1:
- house1) {
- for (Person person2:
- house2) {
- for (Person person3:
- house3) {
- for (Person person4:
- house4) {
- final Person[] people = {
- person0,
- person1,
- person2,
- person3,
- person4
- };
- if (test4(people) && test10(people) && test11(people) && test15(people) && isDistinct(people)) {
- // 找到了正确结果并输出
- for (Person person: people) {
- System.out.println(person);
- }
- }
- }
- }
- }
- }
- }
- }
- // 判断这组人是否有状态重复不重复的情况下应该每种属性的值只有一个人有
- private boolean isDistinct(final Person...people) {
- boolean[] colors = new boolean[5];
- boolean[] nations = new boolean[5];
- boolean[] drinks = new boolean[5];
- boolean[] pets = new boolean[5];
- boolean[] cigarettes = new boolean[5];
- for (int i = 0; i < 5; i++) {
- colors[people[i].color.ordinal()] = true;
- nations[people[i].nation.ordinal()] = true;
- drinks[people[i].drink.ordinal()] = true;
- pets[people[i].pet.ordinal()] = true;
- cigarettes[people[i].cigarette.ordinal()] = true;
- }
- boolean result = true;
- for (int i = 0; i < 5; i++) {
- result &= (colors[i] && nations[i] && drinks[i] && pets[i] && cigarettes[i]);
- }
- return result;
- }
- private boolean test4(final Person...people) {
- int green = 0;
- int white = 0;
- for (Person person: people) {
- if (person.color == COLOR.Green) green = person.index;
- if (person.color == COLOR.White) white = person.index;
- }
- return green + 1 == white;
- }
- private boolean test10(final Person...people) {
- int blends = 0;
- int cat = 0;
- for (Person person: people) {
- if (person.cigarette == CIGARETTE.Blends) blends = person.index;
- if (person.pet == PET.Cat) cat = person.index;
- }
- return (blends + 1 == cat) || (blends - 1 == cat);
- }
- private boolean test11(final Person...people) {
- int horse = 0;
- int dunhill = 0;
- for (Person person: people) {
- if (person.cigarette == CIGARETTE.Dunhill) dunhill = person.index;
- if (person.pet == PET.Horse) horse = person.index;
- }
- return (horse + 1 == dunhill) || (horse - 1 == dunhill);
- }
- private boolean test15(final Person...people) {
- int blends = 0;
- int water = 0;
- for (Person person: people) {
- if (person.cigarette == CIGARETTE.Blends) blends = person.index;
- if (person.drink == DRINK.Water) water = person.index;
- }
- return (blends + 1 == water) || (blends - 1 == water);
- }
- public static void main(String[] args) {
- new Einstein().search();
- }
- }
来源: http://blog.csdn.net/Q_AN1314/article/details/79499428