前回の問題よりさらに複雑な以下のZebra Puzzleを制約論理プログラミングで解いてみる
参照：https://en.wikipedia.org/wiki/Zebra_Puzzle
問題：
The following version of the puzzle appeared in Life International in 1962:
There are five houses.
The Englishman lives in the red house.
The Spaniard owns the dog.
Coffee is drunk in the green house.
The Ukrainian drinks tea.
The green house is immediately to the right of the ivory house.
The Old Gold smoker owns snails.
Kools are smoked in the yellow house.
Milk is drunk in the middle house.
The Norwegian lives in the first house.
The man who smokes Chesterfields lives in the house next to the man with the fox.
Kools are smoked in the house next to the house where the horse is kept.
The Lucky Strike smoker drinks orange juice.
The Japanese smokes Parliaments.
The Norwegian lives next to the blue house.
Now, who drinks water? Who owns the zebra?
In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets [sic]. One other thing: in statement 6, right means your right.
プログラム
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 |
:-use_module(library(clpfd)). zebra_prob:- % left ------> right House=[Color1,Color2,Color3,Color4,Color5], Pet=[Pet1,Pet2,Pet3,Pet4,Pet5], Race=[Race1,Race2,Race3,Race4,Race5], Drink=[Bev1,Bev2,Bev3,Bev4,Bev5], Smoke=[Cig1,Cig2,Cig3,Cig4,Cig5], % Race 1:English 2:Spaniard 3:Ukrainian 4:Norwegian 5:Japanese % HouseColor 1:red 2:green 3:ivory 4:yellow 5:blue % Pet 1:dog 2:snails 3:fox 4:horse 5:zebra % Drink 1:coffee 2:tea 3:milk 4:orange juice 5:water % Smoke 1:Old Gold 2:Kool 3:Chesterfields 4:Lucky Strike 5:Parliaments all_different(House), %それぞれ異なる色の家 all_different(Pet), %それぞれ異なるペット all_different(Race), %それぞれ異なる国籍 all_different(Drink), %それぞれ異なる飲料 all_different(Smoke), %それぞれ異なるタバコ House ins 1..5, Pet ins 1..5, Race ins 1..5, Drink ins 1..5, Smoke ins 1..5, % The Englishman(1) lives in the red house(1). Race1 #= 1 #<==> Color1 #= 1, Race2 #= 1 #<==> Color2 #= 1, Race3 #= 1 #<==> Color3 #= 1, Race4 #= 1 #<==> Color4 #= 1, Race5 #= 1 #<==> Color5 #= 1, % The Spaniard(2) owns the dog(1). Race1 #= 2 #<==> Pet1 #= 1, Race2 #= 2 #<==> Pet2 #= 1, Race3 #= 2 #<==> Pet3 #= 1, Race4 #= 2 #<==> Pet4 #= 1, Race5 #= 2 #<==> Pet5 #= 1, % Coffee(1) is drunk in the green house(2). Bev1 #= 1 #<==> Color1 #= 2, Bev2 #= 1 #<==> Color2 #= 2, Bev3 #= 1 #<==> Color3 #= 2, Bev4 #= 1 #<==> Color4 #= 2, Bev5 #= 1 #<==> Color5 #= 2, % The Ukrainian(3) drinks tea(2). Race1 #= 3 #<==> Bev1 #= 2, Race2 #= 3 #<==> Bev2 #= 2, Race3 #= 3 #<==> Bev3 #= 2, Race4 #= 3 #<==> Bev4 #= 2, Race5 #= 3 #<==> Bev5 #= 2, % The green house(2) is immediately to the right of the ivory house(3). Color1 #= 3 #<==> Color2 #= 2 , Color2 #= 3 #<==> Color3 #= 2 , Color3 #= 3 #<==> Color4 #= 2 , Color4 #= 3 #<==> Color5 #= 2 , % So, green house(2) is not leftmost. Color1 #\= 2, % The Old Gold(1) smoker owns snails(2). Cig1 #= 1 #<==> Pet1 #= 2, Cig2 #= 1 #<==> Pet2 #= 2, Cig3 #= 1 #<==> Pet3 #= 2, Cig4 #= 1 #<==> Pet4 #= 2, Cig5 #= 1 #<==> Pet5 #= 2, % Kools(2) are smoked in the yellow(4) house. Cig1 #= 2 #<==> Color1 #= 4, Cig2 #= 2 #<==> Color2 #= 4, Cig3 #= 2 #<==> Color3 #= 4, Cig4 #= 2 #<==> Color4 #= 4, Cig5 #= 2 #<==> Color5 #= 4, % Milk(3) is drunk in the middle house. Bev3 #= 3, % The Norwegian(4) lives in the first house. (I assume that "first" means leftmost) Race1 #= 4, % The man who smokes Chesterfields(3) lives in the house next to the man with the fox(3). (Cig1 #= 3 #/\ Pet2 #= 3) #\/ (Cig2 #= 3 #/\ Pet3 #= 3) #\/ (Cig3 #= 3 #/\ Pet4 #= 3) #\/ (Cig4 #= 3 #/\ Pet5 #= 3) #\/ (Pet1 #= 3 #/\ Cig2 #= 3) #\/ (Pet2 #= 3 #/\ Cig3 #= 3) #\/ (Pet3 #= 3 #/\ Cig4 #= 3) #\/ (Pet4 #= 3 #/\ Cig5 #= 3) , % Kools(2) are smoked in the house next to the house where the horse(4) is kept. (Cig1 #= 2 #/\ Pet2 #= 4) #\/ (Cig2 #= 2 #/\ Pet3 #= 4) #\/ (Cig3 #= 2 #/\ Pet4 #= 4) #\/ (Cig4 #= 2 #/\ Pet5 #= 4) #\/ (Pet1 #= 4 #/\ Cig2 #= 2) #\/ (Pet2 #= 4 #/\ Cig3 #= 2) #\/ (Pet3 #= 4 #/\ Cig4 #= 2) #\/ (Pet4 #= 4 #/\ Cig5 #= 2) , % The Lucky Strike(4) smoker drinks orange juice(4). Cig1 #= 4 #<==> Bev1 #= 4, Cig2 #= 4 #<==> Bev2 #= 4, Cig3 #= 4 #<==> Bev3 #= 4, Cig4 #= 4 #<==> Bev4 #= 4, Cig5 #= 4 #<==> Bev5 #= 4, % The Japanese(5) smokes Parliaments(5). Race1 #= 5 #<==> Cig1 #= 5, Race2 #= 5 #<==> Cig2 #= 5, Race3 #= 5 #<==> Cig3 #= 5, Race4 #= 5 #<==> Cig4 #= 5, Race5 #= 5 #<==> Cig5 #= 5, % The Norwegian(4) lives next to the blue house(5). (Race1 #= 4 #/\ Color2 #= 5) #\/ (Race2 #= 4 #/\ Color3 #= 5) #\/ (Race3 #= 4 #/\ Color4 #= 5) #\/ (Race4 #= 4 #/\ Color5 #= 5) #\/ (Color1 #= 5 #/\ Race2 #= 4) #\/ (Color2 #= 5 #/\ Race3 #= 4) #\/ (Color3 #= 5 #/\ Race4 #= 4) #\/ (Color4 #= 5 #/\ Race5 #= 4) , label(House), label(Pet), label(Race), label(Smoke), label(Drink), write('house:'),write(House),nl, write('pet:'),write(Pet),nl, write('race:'),write(Race),nl, write('drink:'),write(Drink),nl, write('smoke:'),write(Smoke),nl,nl. |
実行結果
|
1 2 3 4 5 6 7 8 9 |
[3] 23 ?- zebra_prob. house:[4,5,1,3,2] pet:[3,4,2,1,5] race:[4,3,1,2,5] drink:[5,2,3,4,1] smoke:[2,3,1,4,5] true ; false. |
解説
% Race 1:English 2:Spaniard 3:Ukrainian 4:Norwegian 5:Japanese
% HouseColor 1:red 2:green 3:ivory 4:yellow 5:blue
% Pet 1:dog 2:snails 3:fox 4:horse 5:zebra
% Drink 1:coffee 2:tea 3:milk 4:orange juice 5:water
% Smoke 1:Old Gold 2:Kool 3:Chesterfields 4:Lucky Strike 5:Parliaments
Now, who drinks water? Who owns the zebra?
5:water を飲んでいるのは 4:Norwegian
5:zebra を飼っているのは 5:Japanese
単純に条件を書いていけば簡単にプログラミングできたのですが、”next to” の制約を書く書き方で若干間違えた（解が増えてしまった）のとスペルミスなどのチェックが面倒くさかった。