程序化地解决“谁拥有斑马”？

小开

以下是使用 NSolver的完全解决方案节选，张贴在 爱因斯坦的谜语:

// 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));

小开

我是这样做的，首先生成所有有序的 n 元组

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

其中的5 ^ 6,15625，很容易管理。然后过滤掉简单的布尔条件。这里有10个条件，每个条件你都可以过滤掉8/25的条件(1/25的条件包含一个瑞典人和一只狗，16/25的条件包含一个非瑞典人和一只非狗)。当然，他们并不是独立的，但是在过滤掉这些人之后，应该不会剩下太多了。

在那之后，你会得到一个很好的图形问题。创建一个图，其中每个节点代表一个剩余的 n 元组。如果图的两端包含重复的 n 元组位置或违反任何“位置”约束(有五个重复的位置) ，则向图中添加边。从这里开始，您几乎到家了，在图中搜索一个由五个节点组成的独立集合(没有一个节点是由边连接的)。如果没有太多的元组，那么您可能只需要详尽地生成所有的 n 元组的5个元组，然后再次过滤它们。

这可能是一个很好的候选代码高尔夫球。也许有人可以用 Haskell 这样的代码一行就解出来:)

事后想想: 初始过滤通道也可以消除位置约束中的信息。不多(1/25) ，但仍然很重要。

小开

一个帖子已经提到 Prolog 是一个潜在的解决方案。这是真的，我会用这个解决方案。更一般地说，这是自动推理系统的一个完美问题。Prolog 是一种逻辑编程语言(以及相关的解释器) ，构成了这样一个系统。它基本上允许从使用一阶逻辑的语句中总结事实。FOL 基本上是一种更高级的命题逻辑形式。如果您决定不使用 Prolog，可以使用您自己创建的类似系统，使用诸如作案手法之类的技术来执行得出结论。

当然，你需要添加一些关于斑马的规则，因为它在任何地方都没有被提及... ... 我相信你的意图是，你可以找出其他4个宠物，从而推断出最后一个是斑马？您需要添加规则，规定斑马是宠物之一，并且每个房子只能有一个宠物。将这种“常识”知识融入推理系统是将该技术用作真正的人工智能的主要障碍。有一些研究项目，如 Cyc，正试图通过蛮力提供这样的共同知识。他们取得了很大的成功。

小开

最佳答案

下面是基于约束编程的 Python 解决方案:

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.5 GHz)。
答案是“德国人拥有斑马”

通过 pip安装 constraint模块: Pip 安装 python 约束

手动安装:

下载:

$wget < a href = “ https://pypi.python.org/package/source/p/python-約束/python-約束-1.2.tar.bz2 # md5 = d58de49c85992493db53fcb59b9a0a45”rel = “ norefrer”> https://pypi.python.org/packages/source/p/python-constraint/python-constraint-1.2.tar.bz2#md5=d58de49c85992493db53fcb59b9a0a45
提取(Linux/Mac/BSD) :

$bzip2-cd python-約束 -1.2.tar.bz2 | tar xvf-
解压(Windows，带 7zip) :

> 7z e python-約束-1.2.tar. bz2
> 7z e python-約束 -1.2.tar
安装:

$cd python-約束 -1.2
$python setup.py install

小开

在 PAIP (第11章)中，Norvig 使用嵌入在 Lisp 中的 Prolog 解决了斑马难题。

小开

这实际上是一个约束求解问题。您可以通过类似语言的逻辑编程中的一种广义约束传播来实现。我们有一个专门针对 ALE (属性逻辑引擎)系统中的 Zebra 问题的演示:

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

下面是一个简化的斑马拼图的编码链接:

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

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

小开

兼容 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

小开

在 Prolog，我们可以通过选择元素来自 it: 来实例化域(为了提高效率，可以使用 互相排斥的选择),

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.

小开

以下是中华电力有限公司(中电)的简单解决方案(另见香港警务处) :

:- 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.016 CPU/0.020秒(78% CPU，7166493 Lips)
Z = 德语。

小开

另一个 Python 解决方案，这次使用 Python 的 PyKE (Python 知识引擎)。当然，它比@J 在解决方案中使用 Python 的“约束”模块更加详细。塞巴斯蒂安，但它提供了一个有趣的比较，为任何人查看原始知识引擎的这种类型的问题。

线索 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.

人际关系

#############
# 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)

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

小开

ES6(Javascript)解决方案

与大量的 ES6发电机和一点点的浪荡。你将需要巴别塔来运行这个。

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.5秒，但是通过更改规则的顺序可以大大改进这一点。为了清楚起见，我决定保留原订单。

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

小开

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.");
}

小开

这是一个 MiniZn 解决方案，用于解决维基百科中定义的斑马难题:

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

小开

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

下面是一个简单的 F # 解决方案，它来自于 F # 日记中的一篇文章:

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 ]

以9毫秒计算的输出如下:

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"])]

小开

这里有一个编程解决方案的例子(最初是为类似的问题编写的) : https://puzzle-solvers.readthedocs.io/en/latest/

我实现了一个类之间的关系矩阵，它会在您输入约束时得到更新。API 以 Solver类为中心，您可以使用类别和标签对其进行初始化。然后调用诸如 adjecent_to和 match之类的方法来设置关系。

医生对潜在的逻辑有相当详细的解释。你所描述的正是演示之一。为了回答你的问题，下面是演示的样子:

positions = [1, 2, 3, 4, 5]
nationalities = [
'Englishman', 'Spaniard', 'Ukrainian', 'Norwegian', 'Japanese'
]
colors = ['red', 'green', 'ivory', 'yellow', 'blue']
pets = ['dog', 'snails', 'fox', 'horse', 'ZEBRA']
drinks = ['coffee', 'tea', 'milk', 'orange juice', 'WATER']
cigarettes = [
'Old Gold', 'Kools', 'Chesterfields', 'Lucky Strikes', 'Parliaments'
]


problem = {
'position': positions,
'nationality': nationalities,
'color': colors,
'pet': pets,
'drink': drinks,
'cigarette': cigarettes,
}




solver = Solver(problem)




if __name__ == '__main__':
solver.match('Englishman', 'red')
solver.match('Spaniard', 'dog')
solver.match('coffee', 'green')
solver.match('Ukrainian', 'tea')
solver.greater_than('green', 'ivory', 'position', 1)
solver.match('Old Gold', 'snails')
solver.match('Kools', 'yellow')
solver.match('milk', 3)
solver.match('Norwegian', 1)
solver.adjacent_to('Chesterfields', 'fox', 'position')
solver.adjacent_to('Kools', 'horse', 'position')
solver.match('Lucky Strikes', 'orange juice')
solver.match('Japanese', 'Parliaments')
solver.adjacent_to('Norwegian', 'blue', 'position')


solver.draw(show=False, title=f'After Rules: {solver.edges} Edges')


print(f'Solved? {solver.solved}')
print(f'{solver.category_for("ZEBRA", "nationality")} owns the ZEBRA')
print(f'{solver.category_for("WATER", "nationality")} drinks WATER')

这段代码的优点在于，它可以在一夜之间编写完成，而不是一个经过深思熟虑的产品包，但它仍然可以完成工作。