カテゴリー別アーカイブ: PROLOG

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

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

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

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

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

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.


———————————————————————————————————-

実行結果:

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で、そのほかの組み合わせはないようです。

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

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

問題:水泳大会

水泳大会で、この4人が1位から4位を獲得しました(同順位はありません)。

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

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

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

プログラム:

:-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:真実 0:嘘)]

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

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

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

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

ここ数年のマイブームである制約論理ライブラリを使うと一瞬で解けます。自分が使っているのは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になるまで延々と続く

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