爱因斯坦智力题算法的分析

本文主要是介绍爱因斯坦智力题算法的分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前些天，试着编程解一下爱因斯坦出过一道著名的智力题，多年前就见过，当时尝试编程解决，失败了。经过几年编程实践，不参考别人的，看能不能独立写出一个比较好的算法。

//有五个具有五种不同颜色的房间；每个房间裏分别住著一个不同国籍的人；每个人都在喝一种特定品牌的饮料，
// 抽一特定品牌的香烟，养一特定的宠物；没有任意两个人在抽相同品牌的香烟，或喝相同品牌的饮料，或养相同的宠物。//1.英国人住在红色的房子裏；
//2.瑞典人养狗作为宠物；
//3.丹麦人喝茶；
//4.绿房子紧挨著白房子，在白房子的左边；
//5.绿房子的主人喝咖啡；
//6.抽 Pall Mall 牌香烟的人养鸟；
//7.黄色房子裏的人抽 Dunhill 牌香烟；
//8.住在中间那个房子裏的人喝牛奶；
//9.挪威人住在第一个房子裏(最左边)；
//10.抽 Blends 香烟的人和养猫的人相邻；
//11.养马的人和抽 Dunhill 牌香烟的人相邻；
//12.抽 BlueMaster 牌香烟的人喝啤酒；
//13.德国人抽 Prince 牌香烟；
//14.挪威人和住蓝房子的人相邻；
//15.抽Blends 香烟的人和喝矿泉水的人相邻；

如今以不可同日而语之犀利眼光，一眼发现这些条件真面目，不过是一个个Predicate委托而已。当然先建五个枚举：

    enum Color{Red,Green,Yellow,Blue,White}enum Nation{Britain,Norway,Danmark, Sweden,Germany}enum Pet{Bird,Horse,Cat,Dog,Fish}enum Drink{Tea, Beer, Coffee, Water,Milk}enum Smoke{Blends, BlueMaster, PallMall, DunHill, Prince}

又刷刷刷地敲出了这样的代码：

3. Danish.Drink == Drink.Tea;4. var guyInGreen = AllPeople.First(g=>g.HColor==HColor.Green); var guyInWhite = AllPeople.First(g=>g.HColor==HColor.White); guyInWhite.Position - guyInGreen.Position == 1; 5. guy = AllPeople.Where(g=>g.HColor==HColor.Green||g.Drink ==Drink.Coffee); if(guy.Count() > 1) throw; if(guy.HColor == Green) guy.Drink = Coffee; 
……

写了几段，就意识到不对劲了。主要是每个条件最后一句，是该判断呢，还是该赋值呢？比如说如果一个人，住在红房子里，那他一定是英国人。那就要看这个人有哪些属性已经确定了。

而且，如果既现在既不确定哪个住红房子，也不知道谁是英国人，怎么办？经过反复思考，我想每个条件，除了能提供判断，以及合适时赋值，还要提供推断，即可能的方案以供尝试。先选一种方案，然后下个条件再判断现在的状态是否合法，是的话再提出一组方案，不然就选上一条件中的下一个方案。

想到这里，算法的轮廓大致浮现了出来。每个条件，将成为一个个Condition类的实例。而另一个领域模型，之前没有想到的类，已经呼之欲出，即将登上舞台成为主角。导演，自然是偶了。

这场好戏，现在该考虑故事背景了。想在潘多拉星球上拍神雕侠侣，大概观众会吐血，当然更别说种山楂树，观众不吐我都要吐了。在上下班路上，内心经过痛苦的斗争，偶决定放弃风花雪月的属性，因为给每个属性创建状态标识的成本太高。于是偶移师海阔天空的大自然，不加雕琢的Dictionary成了这部戏的主要外景。

    class Guy{public Dictionary Properties = new Dictionary(6);......}class PN   //PropertyName{public const string Color = "Color";public const string Pet = "Pet";public const string Nation = "Nation";public const string Drink = "Drink";public const string Smoke = "Smoke";public const string Postion = "Postion";public static IEnumerable GetNames(){yield return Postion;yield return Nation;yield return Color;yield return Drink;yield return Pet;yield return Smoke;}}

Guy类的主要函数，就是围绕Guy.Properties这个属性字典进行操作，如何封装取决于Condition类的实现。对于条件中单独一个属性，本来可以用 KeyValuePair<string,int>表示，不过太长，所以自己写了个Property类。要是类型能定义别名就好了。看题目中的条件，不少都是根据位置作判断的，所以位置是特殊的属性，如果能用来作Guy的主键，应该可以事半功倍。

下面，期待中的主角露出了庐山真面目，完全是我们以抽象思维创作出来艺术形像。其实很简单，但没艺术细胞的想不出，不会创作的写不出，大家认为呢？

   class Attempt{public Guy[] Guys = new Guy[2];public Property[] Properties = new Property[2];public void Act(){Guys[0].SetProperty(Properties[0]);if(Guys[1] !=null) Guys[1].SetProperty(Properties[1]);}public void RollBack(){Guys[0].RemoveProperty(Properties[0]);if (Guys[1] != null) Guys[1].RemoveProperty(Properties[1]);}public Attempt(Property[] properties, Guy[] guys){Guys = guys;Properties = properties;}public Attempt(Property[] properties, Guy guy){Guys[0] = Guys[1] = guy;Properties = properties;}public Attempt(Property property, Guy guy){Guys[0] = guy;Properties[0] = property;}}

接着来参观下为主角量身打造的舞台吧，大导演拍大片，当然要打造大舞台，比世博园还大，看个样子就行了 :)

  abstract class Condition{protected Property[] Properties = new Property[2];protected Condition(Property p1, Property p2);protected Condition() { }public abstract MatchResult Match(IList guys, ref IList attempts);}/// /// 同人条件/// class SameGuyCondition : Condition{public SameGuyCondition(Property p1, Property p2);public override MatchResult Match(IList guys, ref IList attempts);}/// /// 相邻条件/// class AdjacentCondition : Condition{RelativePosition Relation;  //default is bothpublic AdjacentCondition(Property p1, Property p2);public AdjacentCondition(Property p1, Property p2, RelativePosition relation);public override MatchResult Match(IList guys, ref IList attempts);}

这场戏分十几场来拍，有了前面的准备，剧本一气呵成：

  class Puzzle{static IList conditions = new List();public static void Start(){......AddCondition(PN.Nation, Nation.Britain, PN.Color, Color.Red);AddCondition(PN.Nation, Nation.Sweden, PN.Pet, Pet.Dog);AddCondition(PN.Nation, Nation.Danmark, PN.Drink, Drink.Tea);AddCondition(PN.Color, Color.Green, PN.Color, Color.White, RelativePosition.Left);AddCondition(PN.Color, Color.Green, PN.Drink, Drink.Coffee);AddCondition(PN.Smoke, Smoke.PallMall, PN.Pet, Pet.Bird);AddCondition(PN.Color, Color.Yellow, PN.Smoke, Smoke.DunHill);AddCondition(PN.Postion, 3, PN.Drink, Drink.Milk);AddCondition(PN.Nation, Nation.Norway, PN.Postion, 1);AddCondition(PN.Smoke, Smoke.Blends, PN.Pet, Pet.Cat, RelativePosition.Both );AddCondition(PN.Pet, Pet.Horse, PN.Smoke, Smoke.DunHill, RelativePosition.Both);AddCondition(PN.Smoke, Smoke.BlueMaster, PN.Drink, Drink.Beer);AddCondition(PN.Smoke, Smoke.Prince, PN.Nation, Nation.Germany);AddCondition(PN.Nation, Nation.Norway, PN.Color, Color.Blue, RelativePosition.Both);AddCondition(PN.Drink, Drink.Water, PN.Smoke, Smoke.Blends, RelativePosition.Both);......}}

看上去万事俱备，只欠东风了。事实上要借到东风，还须一些神通，最后一步还有一道难题，这么多场景如何串联在一起？这种戏偶以前从未拍过，考验功底的时候到了。在僵局的时刻，“搜索树”在脑中灵光一现，对，听这名字就是我要的。虽然不知所谓，也从未用过，但“树”我懂的啊。实话说，偶很讨厌写这些树啊图啊的，不过关键时刻，难不倒偶的。

  class StepNode{/// /// The number of stage in the search tree, each stage match a condition/// public Int32 Index;StepNode[] Steps;public StepNode Parent;public Attempt Action;/// /// The index indicates which step should be continued now, the previous steps has failed./// Int32 currentStepIndex;Boolean Ending{get{if (Steps == null) return true;return currentStepIndex >= Steps.Length;}}public StepNode Next(){StepNode nextNode;if (Ending){if (Action != null) Action.RollBack(); nextNode = Parent.Next();}else nextNode = Steps[currentStepIndex];currentStepIndex++;return nextNode;}public StepNode Expand(IList attempts){if (attempts != null || attempts.Count > 0){Steps = new StepNode[attempts.Count];for (int i = 0; i < attempts.Count; i++){Steps[i] = new StepNode { Parent = this, Index = Index + 1, Action = attempts[i] };}}else{Steps = new StepNode[] {new StepNode { Parent = this, Index = Index + 1 } };}return this;}}class Puzzle{static IList conditions = new List();static IList attempts = new List();static IList guys;public static void Start(){guys = GuyRuler.Init();#region Init conditions... ...#endregionvar root = new StepNode();GoFrom(root);}static void GoFrom(StepNode node){if (node.Index >= conditions.Count) return;if (node.Action != null) node.Action.Act();var result = conditions[node.Index].Match(guys, ref attempts);if (result == MatchResult.Fail){if (node.Action != null) node.Action.RollBack();node = node.Parent.Next();}else{node = node.Expand(attempts).Next();}GoFrom(node);   }}

非常顺利，人就要敢于尝试和突破。照例，杀青前，测试下结果：