「Zebraの所有者」をプログラムで解決する
https://stackoverflow.com/questions/318888
-
11-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
編集：このパズルは「アインシュタインの謎」とも呼ばれます
Zebraの所有者（ここでオンラインバージョンを試してください）は、パズルの古典的なセットの例ですStack Overflowのほとんどの人はペンと紙でそれを解決できます。しかし、プログラムによるソリューションはどのようになりますか？
下記の手がかりに基づいて...
- 5軒の家があります。
- 各家には独自の色があります。
- すべての住宅所有者の国籍は異なります。
- それらはすべて異なるペットを飼っています。
- すべて異なる飲み物を飲みます。
- 彼らはすべて異なるタバコを吸っています。
- イギリス人は赤い家に住んでいます。
- スウェーデン人には犬がいます。
- デーンはお茶を飲みます。
- グリーンハウスはホワイトハウスの左側にあります。
- 彼らは温室でコーヒーを飲みます。
- ポールモールを吸う男性には鳥がいます。
- 黄色い家ではダンヒルを吸っています。
- ミドルハウスでは牛乳を飲みます。
- ノルウェー人は最初の家に住んでいます。
- Blendを吸う男性は、猫のいる家の隣の家に住んでいます。
- 馬のいる家の隣の家では、ダンヒルを吸っています。
- ブルーマスターを吸う男はビールを飲みます。
- ドイツ人は王子を吸う。
- ノルウェー人は青い家の隣に住んでいます。
- 彼らはBlendを吸う家の隣の家で水を飲みます。
... Zebraの所有者
解決
制約プログラミングに基づく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.5GHz）かかります。
答えは「ドイツはシマウマを所有しています」
pip constraint モジュールをインストールするには>：
pip install python-constraint
手動でインストールするには：
-
ダウンロード：
-
extract（Linux / Mac / BSD）：
$ bzip2 -cd python-constraint-1.2.tar.bz2 | tar xvf-
-
extract（Windows、 7zip を使用）：
＆gt; 7z e python-constraint-1.2.tar.bz2
＆gt; 7z e python-constraint-1.2.tar -
インストール：
$ cd python-constraint-1.2
$ python setup.py install
他のヒント
Prologでは、要素を から選択するだけでドメインをインスタンス化できます:)（効率のために、相互に排他的な選択を行う）。 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が潜在的なソリューションであるとすでに述べました。これは真実であり、私が使用するソリューションです。より一般的に言えば、これは自動推論システムにとって完璧な問題です。プロローグは、そのようなシステムを形成する論理プログラミング言語（および関連するインタープリター）です。基本的に、 First Order Logic を使用して作成されたステートメントから事実を結論付けることができます。 FOLは基本的に命題論理のより高度な形式です。 Prologを使用したくない場合は、 modus ponens が結論を導き出します。
もちろん、シマウマに関するいくつかのルールを追加する必要があります。それはどこにも言及されていないからです...意図は、他の4つのペットを見つけて、最後の1つがシマウマであると推測できることです？シマウマはペットの1つであり、各家には1つのペットしか持てないというルールを追加する必要があります。この種の「常識」を取得する推論システムへの知識は、この技術を真の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、簡単に管理できます。次に、単純なブール条件を除外します。 10個あり、それぞれ条件の8/25を除外すると予想されます（条件の1/25には犬とスウェーデン人が含まれ、16/25には非犬と非スウェーデン人が含まれます） 。もちろん、それらは独立しているわけではありませんが、それらをフィルターで除外した後、多くは残らないはずです。
その後、グラフの問題が発生しました。各ノードが残りのnタプルの1つを表すグラフを作成します。 2つの端にいくつかのnタプル位置に重複が含まれているか、「位置」制約に違反している場合（それらの5つがあります）、グラフにエッジを追加します。そこからほとんど家に帰って、グラフを検索して、5つのノードの独立したセットを検索します（ノードはエッジで接続されていません）。あまり多くない場合は、5タプルのnタプルをすべて網羅的に生成し、再度フィルタリングするだけで済みます。
これはコードゴルフの良い候補になる可能性があります。誰かがおそらくhaskellのようなもので1行で解決できます：）
後付け：最初のフィルターパスでは、位置の制約から情報を削除することもできます。それほど（1/25）ではありませんが、それでも重要です。
別のPythonソリューション。今回はPythonのPyKE（Python Knowledge Engine）を使用します。確かに、Pythonの「制約」を使用するよりも冗長です。 @ J.F.Sebastianによるソリューションのモジュールですが、このタイプの問題の生の知識エンジンを調べている人にとって興味深い比較を提供します。
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.
fullからの抜粋です NSolver を使用したソリューション、 < a href = "http://www.knowing.net/index.php/2005/08/08/einsteins-riddle-in-c/" rel = "nofollow noreferrer"> 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));
CLP（FD）の簡単なソリューションです（ 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？-time（solve（Z））。
％111,798推論、0.020秒で0.016 CPU（78％CPU、7166493唇）
Z =ドイツ語。
ES6（Javascript）ソリューション
ES6ジェネレーターおよび少しの lodash 。これを実行するには、 Babel が必要です。
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秒ですが、ルールの順序を変更することで大幅に改善できます。明確にするために元の順序を維持することにしました。
ありがとう、これはクールな挑戦でした！
これは本当に制約を解決する問題です。言語のような論理プログラミングで一般的な種類の制約伝播を使用してそれを行うことができます。 ALE（属性論理エンジン）システムのZebra問題専用のデモがあります：
http://www.cs.toronto.edu/~gpenn/ale .html
単純化されたZebraパズルのコーディングへのリンクは次のとおりです。
http：//www.cs.toronto。 edu /〜gpenn / ale / files / grammars / baby.pl
これを効率的に行うことは別の問題です。
このような問題をプログラムで解決する最も簡単な方法は、すべての順列でネストされたループを使用し、結果が質問の述語を満たしているかどうかを確認することです。妥当な時間内に答えを計算できるようになるまで計算の複雑さを劇的に減らすために、多くの述語を内側のループから外側のループに引き上げることができます。
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ソリューションです。
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
所属していません StackOverflow
