以编程方式解决“谁拥有斑马”？

编辑：这个难题也被称为“爱因斯坦的谜语”

谁拥有斑马 （你可以尝试这里的在线版本 ）是一个经典的谜题的例子，我敢打赌，大多数人堆栈溢出可以用笔和纸来解决它。 但是一个程序化的解决scheme是什么样的？

根据以下列出的线索…

  • 有五间房子。
  • 每个房子都有自己独特的颜色。
  • 所有的房主都是不同的国籍。
  • 他们都有不同的宠物。
  • 他们都喝不同的饮料。
  • 他们都抽不同的香烟。
  • 英国人住在红房子里。
  • 瑞典人有一只狗。
  • 丹麦人喝茶。
  • 温室在白宫的左边。
  • 他们在温室里喝咖啡。
  • 吸颇尔购物中心的人有鸟。
  • 在黄色的房子，他们吸烟登喜路。
  • 在中间的房子里，他们喝牛奶。
  • 挪威人住在第一宫。
  • 那个抽Blend的男人住在猫屋旁边的房子里。
  • 在他们家有一匹马的房子旁边，他们吸烟登喜路。
  • 抽蓝色大师的人喝啤酒。
  • 德国人吸烟王子。
  • 挪威人住在蓝屋旁边。
  • 他们在房子旁边的房子里喝水，在那里他们抽Blend。

谁拥有斑马？

以下是基于约束编程的Python解决scheme： 

from constraint import AllDifferentConstraint, InSetConstraint, Problem # variables colors = "blue red green white yellow".split() nationalities = "Norwegian German Dane Swede English".split() pets = "birds dog cats horse zebra".split() drinks = "tea coffee milk beer water".split() cigarettes = "Blend, Prince, Blue Master, Dunhill, Pall Mall".split(", ") # There are five houses. minn, maxn = 1, 5 problem = Problem() # value of a variable is the number of a house with corresponding property variables = colors + nationalities + pets + drinks + cigarettes problem.addVariables(variables, range(minn, maxn+1)) # Each house has its own unique color. # All house owners are of different nationalities. # They all have different pets. # They all drink different drinks. # They all smoke different cigarettes. for vars_ in (colors, nationalities, pets, drinks, cigarettes): problem.addConstraint(AllDifferentConstraint(), vars_) # In the middle house they drink milk. #NOTE: interpret "middle" in a numerical sense (not geometrical) problem.addConstraint(InSetConstraint([(minn + maxn) // 2]), ["milk"]) # The Norwegian lives in the first house. #NOTE: interpret "the first" as a house number problem.addConstraint(InSetConstraint([minn]), ["Norwegian"]) # The green house is on the left side of the white house. #XXX: what is "the left side"? (linear, circular, two sides, 2D house arrangment) #NOTE: interpret it as 'green house number' + 1 == 'white house number' problem.addConstraint(lambda a,b: a+1 == b, ["green", "white"]) def add_constraints(constraint, statements, variables=variables, problem=problem): for stmt in (line for line in statements if line.strip()): problem.addConstraint(constraint, [v for v in variables if v in stmt]) and_statements = """ They drink coffee in the green house. The man who smokes Pall Mall has birds. The English man lives in the red house. The Dane drinks tea. In the yellow house they smoke Dunhill. The man who smokes Blue Master drinks beer. The German smokes Prince. The Swede has a dog. """.split("\n") add_constraints(lambda a,b: a == b, and_statements) nextto_statements = """ The man who smokes Blend lives in the house next to the house with cats. In the house next to the house where they have a horse, they smoke Dunhill. The Norwegian lives next to the blue house. They drink water in the house next to the house where they smoke Blend. """.split("\n") #XXX: what is "next to"? (linear, circular, two sides, 2D house arrangment) add_constraints(lambda a,b: abs(a - b) == 1, nextto_statements) def solve(variables=variables, problem=problem): from itertools import groupby from operator import itemgetter # find & print solutions for solution in problem.getSolutionIter(): for key, group in groupby(sorted(solution.iteritems(), key=itemgetter(1)), key=itemgetter(1)): print key, for v in sorted(dict(group).keys(), key=variables.index): print v.ljust(9), print if __name__ == '__main__': solve()

输出： 

 1 yellow Norwegian cats water Dunhill 2 blue Dane horse tea Blend 3 red English birds milk Pall Mall 4 green German zebra coffee Prince 5 white Swede dog beer Blue Master

需要0.6秒（CPU 1.5GHz）才能find解决scheme。
答案是“德国人拥有斑马”。

通过pip安装constraint模块 ：pip install python-constraint

手动安装：

在Prolog中，我们可以通过从中select元素来实例化该域（为了效率，做出相互排斥的select ）。 使用SWI-Prolog， 

 select([A|As],S):- select(A,S,S1),select(As,S1). select([],_). left_of(A,B,C):- append(_,[A,B|_],C). next_to(A,B,C):- left_of(A,B,C) ; left_of(B,A,C). zebra(Owns, HS):- % house: color,nation,pet,drink,smokes HS = [ h(_,norwegian,_,_,_), h(blue,_,_,_,_), h(_,_,_,milk,_), _, _], select([ h(red,brit,_,_,_), h(_,swede,dog,_,_), h(_,dane,_,tea,_), h(_,german,_,_,prince)], HS), select([ h(_,_,birds,_,pallmall), h(yellow,_,_,_,dunhill), h(_,_,_,beer,bluemaster)], HS), left_of( h(green,_,_,coffee,_), h(white,_,_,_,_), HS), next_to( h(_,_,_,_,dunhill), h(_,_,horse,_,_), HS), next_to( h(_,_,_,_,blend), h(_,_,cats, _,_), HS), next_to( h(_,_,_,_,blend), h(_,_,_,water,_), HS), member( h(_,Owns,zebra,_,_), HS).

运行相当即时： 

 ?- time( (zebra(Who,HS), writeln(Who), nl, maplist(writeln,HS), nl, false ; writeln('no more solutions!') )). german h( yellow, norwegian, cats, water, dunhill ) h( blue, dane, horse, tea, blend ) h( red, brit, birds, milk, pallmall ) h( green, german, zebra, coffee, prince ) % formatted by hand h( white, swede, dog, beer, bluemaster) no more solutions! % 1,706 inferences, 0.000 CPU in 0.070 seconds (0% CPU, Infinite Lips) true.

一个海报已经提到，Prolog是一个潜在的解决scheme。 这是真的，这是我将使用的解决scheme。 更一般地说，这是一个自动推理系统的完美问题。 Prolog是一个逻辑编程语言（和相关的解释器），形成这样一个系统。 它基本上允许从使用First Order Logic的陈述中得出结论。 FOL基本上是比较高级的命题逻辑forms。 如果你决定不想使用Prolog，你可以使用一种类似于你自己创build的系统，使用诸如modus ponens之类的技术来进行绘制结论。

当然，您将需要添加关于斑马的一些规则，因为它在任何地方都没有提及…我相信的目的是，你可以找出其他4只宠物，从而推断出最后一只是斑马？ 你会想添加规则，说明斑马是宠物之一，每个房子只能有一个宠物。 将这种“常识”知识引入推理系统是将该技术用作真实AI的主要障碍。 有一些研究项目，如Cyc，正试图通过暴力给这种常识。 他们遇到了一个有趣的成功。

SWI-Prolog兼容： 

 % NOTE - This may or may not be more efficent. A bit verbose, though. left_side(L, R, [L, R, _, _, _]). left_side(L, R, [_, L, R, _, _]). left_side(L, R, [_, _, L, R, _]). left_side(L, R, [_, _, _, L, R]). next_to(X, Y, Street) :- left_side(X, Y, Street). next_to(X, Y, Street) :- left_side(Y, X, Street). m(X, Y) :- member(X, Y). get_zebra(Street, Who) :- Street = [[C1, N1, P1, D1, S1], [C2, N2, P2, D2, S2], [C3, N3, P3, D3, S3], [C4, N4, P4, D4, S4], [C5, N5, P5, D5, S5]], m([red, english, _, _, _], Street), m([_, swede, dog, _, _], Street), m([_, dane, _, tea, _], Street), left_side([green, _, _, _, _], [white, _, _, _, _], Street), m([green, _, _, coffee, _], Street), m([_, _, birds, _, pallmall], Street), m([yellow, _, _, _, dunhill], Street), D3 = milk, N1 = norwegian, next_to([_, _, _, _, blend], [_, _, cats, _, _], Street), next_to([_, _, horse, _, _], [_, _, _, _, dunhill], Street), m([_, _, _, beer, bluemaster], Street), m([_, german, _, _, prince], Street), next_to([_, norwegian, _, _, _], [blue, _, _, _, _], Street), next_to([_, _, _, water, _], [_, _, _, _, blend], Street), m([_, Who, zebra, _, _], Street).

在翻译： 

 ?- get_zebra(Street, Who). Street = ... Who = german

这是我怎么去做的。 首先，我会生成所有有序的n元组 

 (housenumber, color, nationality, pet, drink, smoke)

其中5 ^ 6，15625，易于pipe理。 然后我会过滤出简单的布尔条件。 有十个，其中每一个你想过滤出8/25的条件（1/25的条件包含一个瑞典人与狗，16/25包含一个非瑞典人与非狗） 。 当然他们不是独立的，但过滤出来后不应该有太多的离开。

之后，你有一个很好的graphics问题。 用每个节点代表剩余的n元组之一来创build一个图。 如果两端包含一些n元组位置的重复或违反任何“位置”约束（其中有五个），则向图添加边。 从那里你几乎在家，searchgraphics的一个独立的五个节点（没有任何连接的边缘节点）。 如果不是太多的话，你可能只是彻底地生成n元组的所有5元组，然后再对它们进行过滤。

这可能是代码高尔夫的一个很好的候选人。 有人可以解决这个问题，像haskell 🙂

事后考虑：初始过滤通行证还可以消除位置约束的信息。 没有太多（1/25），但仍然显着。

另一个Python解决scheme，这次使用Python的PyKE（Python知识引擎）。 当然，它比@JFSebastian在解决scheme中使用Python的“约束”模块更加冗长，但它为任何正在寻找这种types的问题的原始知识引擎的人提供了一个有趣的比较。

clues.kfb 

 categories( POSITION, 1, 2, 3, 4, 5 ) # There are five houses. categories( HOUSE_COLOR, blue, red, green, white, yellow ) # Each house has its own unique color. categories( NATIONALITY, Norwegian, German, Dane, Swede, English ) # All house owners are of different nationalities. categories( PET, birds, dog, cats, horse, zebra ) # They all have different pets. categories( DRINK, tea, coffee, milk, beer, water ) # They all drink different drinks. categories( SMOKE, Blend, Prince, 'Blue Master', Dunhill, 'Pall Mall' ) # They all smoke different cigarettes. related( NATIONALITY, English, HOUSE_COLOR, red ) # The English man lives in the red house. related( NATIONALITY, Swede, PET, dog ) # The Swede has a dog. related( NATIONALITY, Dane, DRINK, tea ) # The Dane drinks tea. left_of( HOUSE_COLOR, green, HOUSE_COLOR, white ) # The green house is on the left side of the white house. related( DRINK, coffee, HOUSE_COLOR, green ) # They drink coffee in the green house. related( SMOKE, 'Pall Mall', PET, birds ) # The man who smokes Pall Mall has birds. related( SMOKE, Dunhill, HOUSE_COLOR, yellow ) # In the yellow house they smoke Dunhill. related( POSITION, 3, DRINK, milk ) # In the middle house they drink milk. related( NATIONALITY, Norwegian, POSITION, 1 ) # The Norwegian lives in the first house. next_to( SMOKE, Blend, PET, cats ) # The man who smokes Blend lives in the house next to the house with cats. next_to( SMOKE, Dunhill, PET, horse ) # In the house next to the house where they have a horse, they smoke Dunhill. related( SMOKE, 'Blue Master', DRINK, beer ) # The man who smokes Blue Master drinks beer. related( NATIONALITY, German, SMOKE, Prince ) # The German smokes Prince. next_to( NATIONALITY, Norwegian, HOUSE_COLOR, blue ) # The Norwegian lives next to the blue house. next_to( DRINK, water, SMOKE, Blend ) # They drink water in the house next to the house where they smoke Blend.

relations.krb 

 ############# # Categories # Foreach set of categories, assert each type categories foreach clues.categories($category, $thing1, $thing2, $thing3, $thing4, $thing5) assert clues.is_category($category, $thing1) clues.is_category($category, $thing2) clues.is_category($category, $thing3) clues.is_category($category, $thing4) clues.is_category($category, $thing5) ######################### # Inverse Relationships # Foreach A=1, assert 1=A inverse_relationship_positive foreach clues.related($category1, $thing1, $category2, $thing2) assert clues.related($category2, $thing2, $category1, $thing1) # Foreach A!1, assert 1!A inverse_relationship_negative foreach clues.not_related($category1, $thing1, $category2, $thing2) assert clues.not_related($category2, $thing2, $category1, $thing1) # Foreach "A beside B", assert "B beside A" inverse_relationship_beside foreach clues.next_to($category1, $thing1, $category2, $thing2) assert clues.next_to($category2, $thing2, $category1, $thing1) ########################### # Transitive Relationships # Foreach A=1 and 1=a, assert A=a transitive_positive foreach clues.related($category1, $thing1, $category2, $thing2) clues.related($category2, $thing2, $category3, $thing3) check unique($thing1, $thing2, $thing3) \ and unique($category1, $category2, $category3) assert clues.related($category1, $thing1, $category3, $thing3) # Foreach A=1 and 1!a, assert A!a transitive_negative foreach clues.related($category1, $thing1, $category2, $thing2) clues.not_related($category2, $thing2, $category3, $thing3) check unique($thing1, $thing2, $thing3) \ and unique($category1, $category2, $category3) assert clues.not_related($category1, $thing1, $category3, $thing3) ########################## # Exclusive Relationships # Foreach A=1, assert A!2 and A!3 and A!4 and A!5 if_one_related_then_others_unrelated foreach clues.related($category, $thing, $category_other, $thing_other) check unique($category, $category_other) clues.is_category($category_other, $thing_not_other) check unique($thing, $thing_other, $thing_not_other) assert clues.not_related($category, $thing, $category_other, $thing_not_other) # Foreach A!1 and A!2 and A!3 and A!4, assert A=5 if_four_unrelated_then_other_is_related foreach clues.not_related($category, $thing, $category_other, $thingA) clues.not_related($category, $thing, $category_other, $thingB) check unique($thingA, $thingB) clues.not_related($category, $thing, $category_other, $thingC) check unique($thingA, $thingB, $thingC) clues.not_related($category, $thing, $category_other, $thingD) check unique($thingA, $thingB, $thingC, $thingD) # Find the fifth variation of category_other. clues.is_category($category_other, $thingE) check unique($thingA, $thingB, $thingC, $thingD, $thingE) assert clues.related($category, $thing, $category_other, $thingE) ################### # Neighbors: Basic # Foreach "A left of 1", assert "A beside 1" expanded_relationship_beside_left foreach clues.left_of($category1, $thing1, $category2, $thing2) assert clues.next_to($category1, $thing1, $category2, $thing2) # Foreach "A beside 1", assert A!1 unrelated_to_beside foreach clues.next_to($category1, $thing1, $category2, $thing2) check unique($category1, $category2) assert clues.not_related($category1, $thing1, $category2, $thing2) ################################### # Neighbors: Spatial Relationships # Foreach "A beside B" and "A=(at-edge)", assert "B=(near-edge)" check_next_to_either_edge foreach clues.related(POSITION, $position_known, $category, $thing) check is_edge($position_known) clues.next_to($category, $thing, $category_other, $thing_other) clues.is_category(POSITION, $position_other) check is_beside($position_known, $position_other) assert clues.related(POSITION, $position_other, $category_other, $thing_other) # Foreach "A beside B" and "A!(near-edge)" and "B!(near-edge)", assert "A!(at-edge)" check_too_close_to_edge foreach clues.next_to($category, $thing, $category_other, $thing_other) clues.is_category(POSITION, $position_edge) clues.is_category(POSITION, $position_near_edge) check is_edge($position_edge) and is_beside($position_edge, $position_near_edge) clues.not_related(POSITION, $position_near_edge, $category, $thing) clues.not_related(POSITION, $position_near_edge, $category_other, $thing_other) assert clues.not_related(POSITION, $position_edge, $category, $thing) # Foreach "A beside B" and "A!(one-side)", assert "A=(other-side)" check_next_to_with_other_side_impossible foreach clues.next_to($category, $thing, $category_other, $thing_other) clues.related(POSITION, $position_known, $category_other, $thing_other) check not is_edge($position_known) clues.not_related($category, $thing, POSITION, $position_one_side) check is_beside($position_known, $position_one_side) clues.is_category(POSITION, $position_other_side) check is_beside($position_known, $position_other_side) \ and unique($position_known, $position_one_side, $position_other_side) assert clues.related($category, $thing, POSITION, $position_other_side) # Foreach "A left of B"... # ... and "C=(position1)" and "D=(position2)" and "E=(position3)" # ~> assert "A=(other-position)" and "B=(other-position)+1" left_of_and_only_two_slots_remaining foreach clues.left_of($category_left, $thing_left, $category_right, $thing_right) clues.related($category_left, $thing_left_other1, POSITION, $position1) clues.related($category_left, $thing_left_other2, POSITION, $position2) clues.related($category_left, $thing_left_other3, POSITION, $position3) check unique($thing_left, $thing_left_other1, $thing_left_other2, $thing_left_other3) clues.related($category_right, $thing_right_other1, POSITION, $position1) clues.related($category_right, $thing_right_other2, POSITION, $position2) clues.related($category_right, $thing_right_other3, POSITION, $position3) check unique($thing_right, $thing_right_other1, $thing_right_other2, $thing_right_other3) clues.is_category(POSITION, $position4) clues.is_category(POSITION, $position5) check is_left_right($position4, $position5) \ and unique($position1, $position2, $position3, $position4, $position5) assert clues.related(POSITION, $position4, $category_left, $thing_left) clues.related(POSITION, $position5, $category_right, $thing_right) ######################### fc_extras def unique(*args): return len(args) == len(set(args)) def is_edge(pos): return (pos == 1) or (pos == 5) def is_beside(pos1, pos2): diff = (pos1 - pos2) return (diff == 1) or (diff == -1) def is_left_right(pos_left, pos_right): return (pos_right - pos_left == 1)

driver.py （实际上更大，但这是本质） 

 from pyke import knowledge_engine engine = knowledge_engine.engine(__file__) engine.activate('relations') try: natl = engine.prove_1_goal('clues.related(PET, zebra, NATIONALITY, $nationality)')[0].get('nationality') except Exception, e: natl = "Unknown" print "== Who owns the zebra? %s ==" % natl

示例输出： 

 $ python driver.py == Who owns the zebra? German == # Color Nationality Pet Drink Smoke ======================================================= 1 yellow Norwegian cats water Dunhill 2 blue Dane horse tea Blend 3 red English birds milk Pall Mall 4 green German zebra coffee Prince 5 white Swede dog beer Blue Master Calculated in 1.19 seconds.

来源： https ： //github.com/DreadPirateShawn/pyke-who-owns-zebra

下面是使用NSolver 完整解决scheme的摘录，发布在爱因斯坦的谜语在C＃中 ： 

 // The green house's owner drinks coffee Post(greenHouse.Eq(coffee)); // The person who smokes Pall Mall rears birds Post(pallMall.Eq(birds)); // The owner of the yellow house smokes Dunhill Post(yellowHouse.Eq(dunhill));

在PAIP（第11章）中，Norvig使用embedded在Lisp中的Prolog解决了斑马谜题 。

ES6（Javascript）解决scheme

有大量的ES6发电机和一点点lodash 。 你需要巴别来运行这个。 

 var _ = require('lodash'); function canBe(house, criteria) { for (const key of Object.keys(criteria)) if (house[key] && house[key] !== criteria[key]) return false; return true; } function* thereShouldBe(criteria, street) { for (const i of _.range(street.length)) yield* thereShouldBeAtIndex(criteria, i, street); } function* thereShouldBeAtIndex(criteria, index, street) { if (canBe(street[index], criteria)) { const newStreet = _.cloneDeep(street); newStreet[index] = _.assign({}, street[index], criteria); yield newStreet; } } function* leftOf(critA, critB, street) { for (const i of _.range(street.length - 1)) { if (canBe(street[i], critA) && canBe(street[i+1], critB)) { const newStreet = _.cloneDeep(street); newStreet[i ] = _.assign({}, street[i ], critA); newStreet[i+1] = _.assign({}, street[i+1], critB); yield newStreet; } } } function* nextTo(critA, critB, street) { yield* leftOf(critA, critB, street); yield* leftOf(critB, critA, street); } const street = [{}, {}, {}, {}, {}]; // five houses // Btw: it turns out we don't need uniqueness constraint. const constraints = [ s => thereShouldBe({nation: 'English', color: 'red'}, s), s => thereShouldBe({nation: 'Swede', animal: 'dog'}, s), s => thereShouldBe({nation: 'Dane', drink: 'tea'}, s), s => leftOf({color: 'green'}, {color: 'white'}, s), s => thereShouldBe({drink: 'coffee', color: 'green'}, s), s => thereShouldBe({cigarettes: 'PallMall', animal: 'birds'}, s), s => thereShouldBe({color: 'yellow', cigarettes: 'Dunhill'}, s), s => thereShouldBeAtIndex({drink: 'milk'}, 2, s), s => thereShouldBeAtIndex({nation: 'Norwegian'}, 0, s), s => nextTo({cigarettes: 'Blend'}, {animal: 'cats'}, s), s => nextTo({animal: 'horse'}, {cigarettes: 'Dunhill'}, s), s => thereShouldBe({cigarettes: 'BlueMaster', drink: 'beer'}, s), s => thereShouldBe({nation: 'German', cigarettes: 'Prince'}, s), s => nextTo({nation: 'Norwegian'}, {color: 'blue'}, s), s => nextTo({drink: 'water'}, {cigarettes: 'Blend'}, s), s => thereShouldBe({animal: 'zebra'}, s), // should be somewhere ]; function* findSolution(remainingConstraints, street) { if (remainingConstraints.length === 0) yield street; else for (const newStreet of _.head(remainingConstraints)(street)) yield* findSolution(_.tail(remainingConstraints), newStreet); } for (const streetSolution of findSolution(constraints, street)) { console.log(streetSolution); }

结果： 

 [ { color: 'yellow', cigarettes: 'Dunhill', nation: 'Norwegian', animal: 'cats', drink: 'water' }, { nation: 'Dane', drink: 'tea', cigarettes: 'Blend', animal: 'horse', color: 'blue' }, { nation: 'English', color: 'red', cigarettes: 'PallMall', animal: 'birds', drink: 'milk' }, { color: 'green', drink: 'coffee', nation: 'German', cigarettes: 'Prince', animal: 'zebra' }, { nation: 'Swede', animal: 'dog', color: 'white', cigarettes: 'BlueMaster', drink: 'beer' } ]

运行时间对我来说大约是2.5s，但是通过改变规则的顺序可以大大提高。 我决定保持原始的清晰度。

谢谢，这是一个很酷的挑战！

这是CLP（FD）的简单解决scheme（另请参阅clpfd ）： 

 :- use_module(library(clpfd)). solve(ZebraOwner) :- maplist( init_dom(1..5), [[British, Swedish, Danish, Norwegian, German], % Nationalities [Red, Green, Blue, White, Yellow], % Houses [Tea, Coffee, Milk, Beer, Water], % Beverages [PallMall, Blend, Prince, Dunhill, BlueMaster], % Cigarettes [Dog, Birds, Cats, Horse, Zebra]]), % Pets British #= Red, % Hint 1 Swedish #= Dog, % Hint 2 Danish #= Tea, % Hint 3 Green #= White - 1 , % Hint 4 Green #= Coffee, % Hint 5 PallMall #= Birds, % Hint 6 Yellow #= Dunhill, % Hint 7 Milk #= 3, % Hint 8 Norwegian #= 1, % Hint 9 neighbor(Blend, Cats), % Hint 10 neighbor(Horse, Dunhill), % Hint 11 BlueMaster #= Beer, % Hint 12 German #= Prince, % Hint 13 neighbor(Norwegian, Blue), % Hint 14 neighbor(Blend, Water), % Hint 15 memberchk(Zebra-ZebraOwner, [British-british, Swedish-swedish, Danish-danish, Norwegian-norwegian, German-german]). init_dom(R, L) :- all_distinct(L), L ins R. neighbor(X, Y) :- (X #= (Y - 1)) #\/ (X #= (Y + 1)).

运行它会产生：

3？ – 时间（求解（Z））。
％，推理结果为111,798，0.020秒的CPU为0.016（78％的CPU，7166493个唇部）
Z =德语。

这实际上是一个约束解决问题。 你可以用语言中的逻辑编程来进行广义的约束传播。 我们在ALE（属性逻辑引擎）系统中专门针对Zebra问题进行了演示：

http://www.cs.toronto.edu/~gpenn/ale.html

以下是一个简化的Zebra拼图编码的链接：

http://www.cs.toronto.edu/~gpenn/ale/files/grammars/baby.pl

要有效地做到这一点是另一回事。

以编程方式解决这些问题的最简单方法是在所有排列上使用嵌套循环，并检查结果是否满足问题中的谓词。 许多谓词可以从内部循环升级到外部循环，以便大大降低计算复杂度，直到答案可以在合理的时间内计算。

这里是从F＃Journal中的一篇文章导出的一个简单的F＃解决scheme： 

 let rec distribute y xs = match xs with | [] -> [[y]] | x::xs -> (y::x::xs)::[for xs in distribute y xs -> x::xs] let rec permute xs = match xs with | [] | [_] as xs -> [xs] | x::xs -> List.collect (distribute x) (permute xs) let find xs x = List.findIndex ((=) x) xs + 1 let eq xs x ys y = find xs x = find ys y let nextTo xs x ys y = abs(find xs x - find ys y) = 1 let nations = ["British"; "Swedish"; "Danish"; "Norwegian"; "German"] let houses = ["Red"; "Green"; "Blue"; "White"; "Yellow"] let drinks = ["Milk"; "Coffee"; "Water"; "Beer"; "Tea"] let smokes = ["Blend"; "Prince"; "Blue Master"; "Dunhill"; "Pall Mall"] let pets = ["Dog"; "Cat"; "Zebra"; "Horse"; "Bird"] [ for nations in permute nations do if find nations "Norwegian" = 1 then for houses in permute houses do if eq nations "British" houses "Red" && find houses "Green" = find houses "White"-1 && nextTo nations "Norwegian" houses "Blue" then for drinks in permute drinks do if eq nations "Danish" drinks "Tea" && eq houses "Green" drinks "Coffee" && 3 = find drinks "Milk" then for smokes in permute smokes do if eq houses "Yellow" smokes "Dunhill" && eq smokes "Blue Master" drinks "Beer" && eq nations "German" smokes "Prince" && nextTo smokes "Blend" drinks "Water" then for pets in permute pets do if eq nations "Swedish" pets "Dog" && eq smokes "Pall Mall" pets "Bird" && nextTo pets "Cat" smokes "Blend" && nextTo pets "Horse" smokes "Dunhill" then yield nations, houses, drinks, smokes, pets ]

在9ms中获得的输出是： 

 val it : (string list * string list * string list * string list * string list) list = [(["Norwegian"; "Danish"; "British"; "German"; "Swedish"], ["Yellow"; "Blue"; "Red"; "Green"; "White"], ["Water"; "Tea"; "Milk"; "Coffee"; "Beer"], ["Dunhill"; "Blend"; "Pall Mall"; "Prince"; "Blue Master"], ["Cat"; "Horse"; "Bird"; "Zebra"; "Dog"])]

Microsoft Solver Foundation示例来自： https : //msdn.microsoft.com/en-us/library/ff525831%28v=vs.93%29.aspx?f=255&MSPPError=-2147217396 

 delegate CspTerm NamedTerm(string name); public static void Zebra() { ConstraintSystem S = ConstraintSystem.CreateSolver(); var termList = new List<KeyValuePair<CspTerm, string>>(); NamedTerm House = delegate(string name) { CspTerm x = S.CreateVariable(S.CreateIntegerInterval(1, 5), name); termList.Add(new KeyValuePair<CspTerm, string>(x, name)); return x; }; CspTerm English = House("English"), Spanish = House("Spanish"), Japanese = House("Japanese"), Italian = House("Italian"), Norwegian = House("Norwegian"); CspTerm red = House("red"), green = House("green"), white = House("white"), blue = House("blue"), yellow = House("yellow"); CspTerm dog = House("dog"), snails = House("snails"), fox = House("fox"), horse = House("horse"), zebra = House("zebra"); CspTerm painter = House("painter"), sculptor = House("sculptor"), diplomat = House("diplomat"), violinist = House("violinist"), doctor = House("doctor"); CspTerm tea = House("tea"), coffee = House("coffee"), milk = House("milk"), juice = House("juice"), water = House("water"); S.AddConstraints( S.Unequal(English, Spanish, Japanese, Italian, Norwegian), S.Unequal(red, green, white, blue, yellow), S.Unequal(dog, snails, fox, horse, zebra), S.Unequal(painter, sculptor, diplomat, violinist, doctor), S.Unequal(tea, coffee, milk, juice, water), S.Equal(English, red), S.Equal(Spanish, dog), S.Equal(Japanese, painter), S.Equal(Italian, tea), S.Equal(1, Norwegian), S.Equal(green, coffee), S.Equal(1, green - white), S.Equal(sculptor, snails), S.Equal(diplomat, yellow), S.Equal(3, milk), S.Equal(1, S.Abs(Norwegian - blue)), S.Equal(violinist, juice), S.Equal(1, S.Abs(fox - doctor)), S.Equal(1, S.Abs(horse - diplomat)) ); bool unsolved = true; ConstraintSolverSolution soln = S.Solve(); while (soln.HasFoundSolution) { unsolved = false; System.Console.WriteLine("solved."); StringBuilder[] houses = new StringBuilder[5]; for (int i = 0; i < 5; i++) houses[i] = new StringBuilder(i.ToString()); foreach (KeyValuePair<CspTerm, string> kvp in termList) { string item = kvp.Value; object house; if (!soln.TryGetValue(kvp.Key, out house)) throw new InvalidProgramException( "can't find a Term in the solution: " + item); houses[(int)house - 1].Append(", "); houses[(int)house - 1].Append(item); } foreach (StringBuilder house in houses) { System.Console.WriteLine(house); } soln.GetNext(); } if (unsolved) System.Console.WriteLine("No solution found."); else System.Console.WriteLine( "Expected: the Norwegian drinking water and the Japanese with the zebra."); }

这是一个在Wikipedia中定义的斑马谜题的MiniZinc解决scheme： 

 include "globals.mzn"; % Zebra puzzle int: nc = 5; % Colors int: red = 1; int: green = 2; int: ivory = 3; int: yellow = 4; int: blue = 5; array[1..nc] of var 1..nc:color; constraint alldifferent([color[i] | i in 1..nc]); % Nationalities int: eng = 1; int: spa = 2; int: ukr = 3; int: nor = 4; int: jap = 5; array[1..nc] of var 1..nc:nationality; constraint alldifferent([nationality[i] | i in 1..nc]); % Pets int: dog = 1; int: snail = 2; int: fox = 3; int: horse = 4; int: zebra = 5; array[1..nc] of var 1..nc:pet; constraint alldifferent([pet[i] | i in 1..nc]); % Drinks int: coffee = 1; int: tea = 2; int: milk = 3; int: orange = 4; int: water = 5; array[1..nc] of var 1..nc:drink; constraint alldifferent([drink[i] | i in 1..nc]); % Smokes int: oldgold = 1; int: kools = 2; int: chesterfields = 3; int: luckystrike = 4; int: parliaments = 5; array[1..nc] of var 1..nc:smoke; constraint alldifferent([smoke[i] | i in 1..nc]); % The Englishman lives in the red house. constraint forall ([nationality[i] == eng <-> color[i] == red | i in 1..nc]); % The Spaniard owns the dog. constraint forall ([nationality[i] == spa <-> pet[i] == dog | i in 1..nc]); % Coffee is drunk in the green house. constraint forall ([color[i] == green <-> drink[i] == coffee | i in 1..nc]); % The Ukrainian drinks tea. constraint forall ([nationality[i] == ukr <-> drink[i] == tea | i in 1..nc]); % The green house is immediately to the right of the ivory house. constraint forall ([color[i] == ivory -> if i<nc then color[i+1] == green else false endif | i in 1..nc]); % The Old Gold smoker owns snails. constraint forall ([smoke[i] == oldgold <-> pet[i] == snail | i in 1..nc]); % Kools are smoked in the yellow house. constraint forall ([smoke[i] == kools <-> color[i] == yellow | i in 1..nc]); % Milk is drunk in the middle house. constraint drink[3] == milk; % The Norwegian lives in the first house. constraint nationality[1] == nor; % The man who smokes Chesterfields lives in the house next to the man with the fox. constraint forall ([smoke[i] == chesterfields -> (if i>1 then pet[i-1] == fox else false endif \/ if i<nc then pet[i+1] == fox else false endif) | i in 1..nc]); % Kools are smoked in the house next to the house where the horse is kept. constraint forall ([smoke[i] == kools -> (if i>1 then pet[i-1] == horse else false endif \/ if i<nc then pet[i+1] == horse else false endif)| i in 1..nc]); %The Lucky Strike smoker drinks orange juice. constraint forall ([smoke[i] == luckystrike <-> drink[i] == orange | i in 1..nc]); % The Japanese smokes Parliaments. constraint forall ([nationality[i] == jap <-> smoke[i] == parliaments | i in 1..nc]); % The Norwegian lives next to the blue house. constraint forall ([color[i] == blue -> (if i > 1 then nationality[i-1] == nor else false endif \/ if i<nc then nationality[i+1] == nor else false endif) | i in 1..nc]); solve satisfy;

解： 

 Compiling zebra.mzn Running zebra.mzn color = array1d(1..5 ,[4, 5, 1, 3, 2]); nationality = array1d(1..5 ,[4, 3, 1, 2, 5]); pet = array1d(1..5 ,[3, 4, 2, 1, 5]); drink = array1d(1..5 ,[5, 2, 3, 4, 1]); smoke = array1d(1..5 ,[2, 3, 1, 4, 5]); ---------- Finished in 47msec
Interesting Posts