Category Archives: PROLOG

前回からの続き　Zebra Puzzleを制約論理プログラミングで解く2

前回の問題よりさらに複雑な以下の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.

プログラム

:-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.

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.

実行結果

[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.

[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” の制約を書く書き方で若干間違えた（解が増えてしまった）のとスペルミスなどのチェックが面倒くさかった。

ゼブラパズル(Zebra Puzzle)を制約論理プログラミングで解く

Leave a reply

以下のパズル（ゼブラパズルというらしい）を制約論理プログラミングで解いてみた。

問題：
1.家が３軒あります。その３軒の家はそれぞれ赤・青・緑で塗られています。そしてその住人は、それぞれ異なる国籍で、それぞれ異なるペットを買っています。
2.イギリス人は赤い家に住んでいます。
3.スペイン人は犬を飼っています。
4.日本人は、猫を飼っている人の右側に住んでいます。
5.猫を飼っている人は青色の家の左に住んでいます。

誰がシマウマを飼っているでしょうか？

プログラム

:-use_module(library(clpfd)).

zebra_prob:-

% left  ------> right
House=[Color1,Color2,Color3],
Pet=[Pet1,Pet2,Pet3],
Race=[Race1,Race2,Race3],

% Race  1:Japanese 2:English 3:Spanish
% Color 1:Red 2:Blue 3:Green
% Pet   1:Cat 2:Dog 3:Zebra

all_different(House), %それぞれ異なる色の家
all_different(Pet),   %それぞれ異なるペット
all_different(Race),  %それぞれ異なる国籍

House ins 1..3,
Pet ins 1..3,
Race ins 1..3,

%イギリス人(2)は赤い家(1)
Color1 #= 1 #<==> Race1 #= 2,
Color2 #= 1 #<==> Race2 #= 2,
Color3 #= 1 #<==> Race3 #= 2,

%スペイン人(3)は犬(2)を飼っている
Race1 #= 3 #<==> Pet1 #= 2,
Race2 #= 3 #<==> Pet2 #= 2,
Race3 #= 3 #<==> Pet3 #= 2,

%日本人(1)は、猫(1)を飼っている人の右側
Pet1 #= 1 #<==> Race2 #= 1,
Pet2 #= 1 #<==> Race3 #= 1,
Race1 #\= 1, %日本人は一番左ではない

%猫(1)を飼っている人は青色の家(2)の左に住んでいます。
Pet1 #= 1 #<==> Color2 #= 2,
Pet2 #= 1 #<==> Color3 #= 2,
Pet3 #\= 1, %猫は一番右ではない

label(House),
label(Pet),
label(Race),
write('house:'),write(House),nl,
write('pet:'),write(Pet),nl,
write('race:'),write(Race).

:-use_module(library(clpfd)).

zebra_prob:-

% left ------> right

House=[Color1,Color2,Color3],

Pet=[Pet1,Pet2,Pet3],

Race=[Race1,Race2,Race3],

% Race 1:Japanese 2:English 3:Spanish

% Color 1:Red 2:Blue 3:Green

% Pet 1:Cat 2:Dog 3:Zebra

all_different(House), %それぞれ異なる色の家

all_different(Pet), %それぞれ異なるペット

all_different(Race), %それぞれ異なる国籍

House ins 1..3,

Pet ins 1..3,

Race ins 1..3,

%イギリス人(2)は赤い家(1)

Color1 #= 1 #<==> Race1 #= 2,

Color2 #= 1 #<==> Race2 #= 2,

Color3 #= 1 #<==> Race3 #= 2,

%スペイン人(3)は犬(2)を飼っている

Race1 #= 3 #<==> Pet1 #= 2,

Race2 #= 3 #<==> Pet2 #= 2,

Race3 #= 3 #<==> Pet3 #= 2,

%日本人(1)は、猫(1)を飼っている人の右側

Pet1 #= 1 #<==> Race2 #= 1,

Pet2 #= 1 #<==> Race3 #= 1,

Race1 #\= 1, %日本人は一番左ではない

%猫(1)を飼っている人は青色の家(2)の左に住んでいます。

Pet1 #= 1 #<==> Color2 #= 2,

Pet2 #= 1 #<==> Color3 #= 2,

Pet3 #\= 1, %猫は一番右ではない

label(House),

label(Pet),

label(Race),

write('house:'),write(House),nl,

write('pet:'),write(Pet),nl,

write('race:'),write(Race).

実行結果

1 ?- zebra_prob.
house:[1,2,3]
pet:[1,3,2]
race:[2,1,3]
true ;
house:[3,1,2]
pet:[2,1,3]
race:[3,2,1]
true.

1 ?- zebra_prob.

house:[1,2,3]

pet:[1,3,2]

race:[2,1,3]

true ;

house:[3,1,2]

pet:[2,1,3]

race:[3,2,1]

true.

解説
Race 1:Japanese 2:English 3:Spanish
Color 1:Red 2:Blue 3:Green
Pet 1:Cat 2:Dog 3:Zebra
PetがZebra(3)と同じ要素番号のRaceは必ず1(日本人)
よってシマウマは日本人が飼っている。
家、ペット、国籍の並びの組み合わせは上記2パターンある。

※　「～の右に」という文章を「１軒右」と解釈しています。
　　（２軒右も含むというコードに変更するのも簡単です）

みなみとかおりの数字当て問題を制約論理プログラミングで解く

Leave a reply

ネットで以下のような問題が出ていた。（「これが解けるような秀才は募集しておりません」という塾の広告の問題？）

問題：
みなみとかおりの二人が数当てゲームをしていて、さやかが横で見ている。

このゲームは二人が1～13のトランプのカードの中から1枚取り、
先に相手の数字を当てた方が勝ちになるもので、みなみとかおりは自分のカードの数字しか見ることはできないが、さやかは二人のカードの数字を見ている。
3人が次の順で会話したとき、みなみとかおりのカードの数字を答えなさい。

さやか「二人のカードは異なる数字で、どちらも１ではない。片方がもう一方の整数倍の数字になっている」
みなみ「うーん、わからない」
かおり「私もわからない」
みなみ「そうか、今わかった」

3人が嘘をついていないものとして、みなみとかおりのカードの数字を当てなさい。

（※原文から誤解しやすい表記を少し直しています。）

面白そうな問題だったので、自分の好きなSWI-PROLOGとその制約論理ライブラリCLPFDを使用して解いてみた。

以下 SWI-PROLOGのコード

:- use_module(library(clpfd)).

guess_card_number:-
	[Minami,Kaori] ins 2..13, 		% みなみとかおりの数字は1～13で、しかも1ではない
	Baisu in 2..13,					% 整数倍の数値
	Minami #\= Kaori, 				% みなみとかおりの数は異なる
	Minami #= Kaori * Baisu #\/ Kaori #= Minami * Baisu, % 一方がもう一方の整数倍
	
	setof([Minami,Kaori],label([Minami,Kaori]),AllCombinations), %上記を満たすすべての組み合わせを取得
	write('AllCombinations:'),
	write(AllCombinations),nl,
	maplist(nth0(0),AllCombinations,MinamiCand), 	% 現段階でのみなみの候補
	maplist(nth0(1),AllCombinations,KaoriCand),  	% 現段階でのかおりの候補

	% 現段階ではみなみは相手の数字がわからないとのことなので、みなみの数字は MinamiCand 中に複数存在する数字
	appear_times(MinamiCand,Minami,MinamiAppearTimes),
	MinamiAppearTimes #> 1,

	% 現段階ではかおりは相手の数字がわからないとのことなので、かおりの数字は KaoriCand 中に複数存在する数字
	appear_times(KaoriCand,Kaori,KaoriAppearTimes),
	KaoriAppearTimes #> 1,

	% 上記の条件を満たす組み合わせを取得
	setof([Minami,Kaori],label([Minami,Kaori]),NarrowedCombinations),
	write('NarrowedCombinations:'),
	write(NarrowedCombinations),nl,
	
	maplist(nth0(0),NarrowedCombinations,NarrowedMinamiCand), % 現段階でのみなみの候補
	write('NarrowedMinamiCand:'),
	write(NarrowedMinamiCand),nl,

	% 現段階でみなみは相手の数字がわかったとのことなので、NarrowedMinamiCandのなかで1度しか出ない数字がMinamiの数
	appear_times(NarrowedMinamiCand,Minami,MinamiAppearTimes2),
	MinamiAppearTimes2 #= 1,

	% みなみとかおりの数字を推量する
	label([Minami,Kaori]),
	write([Minami,Kaori]).

% appear_times( Lst, Num, Times)
% [Num] appears [Times] times in [Lst]
appear_times(Lst,Num,Times):-
	maplist(eq_b(Num),Lst,Bs),
	sum(Bs,#=,Times).

eq_b(X,Y,B):-(X#=Y) #<==>B.

:- use_module(library(clpfd)).

guess_card_number:-

[Minami,Kaori] ins 2..13, % みなみとかおりの数字は1～13で、しかも1ではない

Baisu in 2..13, % 整数倍の数値

Minami #\= Kaori, % みなみとかおりの数は異なる

Minami #= Kaori * Baisu #\/ Kaori #= Minami * Baisu, % 一方がもう一方の整数倍

setof([Minami,Kaori],label([Minami,Kaori]),AllCombinations), %上記を満たすすべての組み合わせを取得

write('AllCombinations:'),

write(AllCombinations),nl,

maplist(nth0(0),AllCombinations,MinamiCand), % 現段階でのみなみの候補

maplist(nth0(1),AllCombinations,KaoriCand), % 現段階でのかおりの候補

% 現段階ではみなみは相手の数字がわからないとのことなので、みなみの数字は MinamiCand 中に複数存在する数字

appear_times(MinamiCand,Minami,MinamiAppearTimes),

MinamiAppearTimes #> 1,

% 現段階ではかおりは相手の数字がわからないとのことなので、かおりの数字は KaoriCand 中に複数存在する数字

appear_times(KaoriCand,Kaori,KaoriAppearTimes),

KaoriAppearTimes #> 1,

% 上記の条件を満たす組み合わせを取得

setof([Minami,Kaori],label([Minami,Kaori]),NarrowedCombinations),

write('NarrowedCombinations:'),

write(NarrowedCombinations),nl,

maplist(nth0(0),NarrowedCombinations,NarrowedMinamiCand), % 現段階でのみなみの候補

write('NarrowedMinamiCand:'),

write(NarrowedMinamiCand),nl,

% 現段階でみなみは相手の数字がわかったとのことなので、NarrowedMinamiCandのなかで1度しか出ない数字がMinamiの数

appear_times(NarrowedMinamiCand,Minami,MinamiAppearTimes2),

MinamiAppearTimes2 #= 1,

% みなみとかおりの数字を推量する

label([Minami,Kaori]),

write([Minami,Kaori]).

% appear_times( Lst, Num, Times)

% [Num] appears [Times] times in [Lst]

appear_times(Lst,Num,Times):-

maplist(eq_b(Num),Lst,Bs),

sum(Bs,#=,Times).

eq_b(X,Y,B):-(X#=Y) #<==>B.

実行結果：

1 ?- guess_card_number.
AllCombinations:[[2,4],[2,6],[2,8],[2,10],[2,12],[3,6],[3,9],[3,12],[4,2],[4,8],[4,12],[5,10],[6,2],[6,3],[6,12],[8,2],[8,4],[9,3],[10,2],[10,5],[12,2],[12,3],[12,4],[12,6]]
NarrowedCombinations:[[2,4],[2,6],[2,8],[2,10],[2,12],[3,6],[3,12],[4,2],[4,8],[4,12],[6,2],[6,3],[6,12],[8,2],[8,4],[10,2],[12,2],[12,3],[12,4],[12,6]]
NarrowedMinamiCand:[2,2,2,2,2,3,3,4,4,4,6,6,6,8,8,10,12,12,12,12]
[10,2]
true ;
false.

1 ?- guess_card_number.

AllCombinations:[[2,4],[2,6],[2,8],[2,10],[2,12],[3,6],[3,9],[3,12],[4,2],[4,8],[4,12],[5,10],[6,2],[6,3],[6,12],[8,2],[8,4],[9,3],[10,2],[10,5],[12,2],[12,3],[12,4],[12,6]]

NarrowedCombinations:[[2,4],[2,6],[2,8],[2,10],[2,12],[3,6],[3,12],[4,2],[4,8],[4,12],[6,2],[6,3],[6,12],[8,2],[8,4],[10,2],[12,2],[12,3],[12,4],[12,6]]

NarrowedMinamiCand:[2,2,2,2,2,3,3,4,4,4,6,6,6,8,8,10,12,12,12,12]

[10,2]

true ;

false.

みなみが10、かおりが2で、そのほかの組み合わせはないようです。

うそつき娘問題を制約プログラミングで解く

2 Replies

ネットで以下の問題を見つけたのでSWI-PrologのCLPFDライブラリで解いてみた

問題：水泳大会

水泳大会で、この４人が１位から４位を獲得しました（同順位はありません）。

スタート前の予想は下のとおりで、３人が当たり、１人が外れました。

誰が何位だったのでしょう？

ことり「私は１位」
なる　「私はすずより上位」
すず　「私は１位か２位」
あゆ　「私は１位か２位」

プログラム:

:-use_module(library(clpfd)).

solve_girl_order:-
GirlOrderLst = [KotoriOrder,NaruOrder,SuzuOrder,AyuOrder],
GirlOrderLst ins 1..4,
all_different(GirlOrderLst),
HatugenFlgLst = [KotoriHatugenFlg,NaruHatugenFlg,SuzuHatugenFlg,AyuHatugenFlg],
HatugenFlgLst ins 0..1,
appear_times(HatugenFlgLst,0,1),

KotoriHatugenFlg #<==> (KotoriOrder #= 1),
NaruHatugenFlg #<==> (NaruOrder #< SuzuOrder),
SuzuHatugenFlg #<==> (SuzuOrder #= 1 #\/ SuzuOrder #= 2),
AyuHatugenFlg #<==> (AyuOrder #= 1 #\/ AyuOrder #= 2),

label(GirlOrderLst),
label(HatugenFlgLst),
write(GirlOrderLst),
write(HatugenFlgLst).

% appear_times( Lst, Num, Times)
% [Num] appears [Times] times in [Lst]
appear_times(Lst,Num,Times):-
maplist(eq_b(Num),Lst,Bs),
sum(Bs,#=,Times).
eq_b(X,Y,B):-(X#=Y) #<==>B.

:-use_module(library(clpfd)).

solve_girl_order:-

GirlOrderLst = [KotoriOrder,NaruOrder,SuzuOrder,AyuOrder],

GirlOrderLst ins 1..4,

all_different(GirlOrderLst),

HatugenFlgLst = [KotoriHatugenFlg,NaruHatugenFlg,SuzuHatugenFlg,AyuHatugenFlg],

HatugenFlgLst ins 0..1,

appear_times(HatugenFlgLst,0,1),

KotoriHatugenFlg #<==> (KotoriOrder #= 1),

NaruHatugenFlg #<==> (NaruOrder #< SuzuOrder),

SuzuHatugenFlg #<==> (SuzuOrder #= 1 #\/ SuzuOrder #= 2),

AyuHatugenFlg #<==> (AyuOrder #= 1 #\/ AyuOrder #= 2),

label(GirlOrderLst),

label(HatugenFlgLst),

write(GirlOrderLst),

write(HatugenFlgLst).

% appear_times( Lst, Num, Times)

% [Num] appears [Times] times in [Lst]

appear_times(Lst,Num,Times):-

maplist(eq_b(Num),Lst,Bs),

sum(Bs,#=,Times).

eq_b(X,Y,B):-(X#=Y) #<==>B.

実行結果:

[1] 4 ?- girl_order.
[1,3,4,2][1,1,0,1]
true ;
false.

[1] 4 ?- girl_order.

[1,3,4,2][1,1,0,1]

true ;

false.

実行結果は
[ことり順位,なる順位,すず順位,あゆ順位]
[ことり発言,なる発言,すず発言,あゆ発言 (1:真実 0:嘘)]

プログラム作成に10分くらいかかった。

SWI-Prologの制約論理ライブラリ

Leave a reply

ネットで見かけた以下の問題

「自然数のうち、３乗すると下３桁が９９９になるものを１つ挙げよ」

ここ数年のマイブームである制約論理ライブラリを使うと一瞬で解けます。自分が使っているのはSWI-PrologのCLPFDライブラリなのですが、プログラムは以下のみ

X in 1..9999999999999999,X^3 mod 1000 #= 999,label([X]).

実行結果は以下

X = 999 ;
X = 1999 ;
X = 2999 ;
X = 3999 ;
X = 4999 ;
X = 5999 ;
X = 6999 ;
X = 7999 ;
X = 8999 ;
X = 9999 ;
X = 10999　以下Xが9999999999999999になるまで延々と続く

こういう問題を大量に解く必要がある案件があれば是非弊社にお問い合わせ下さい！笑