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

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

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

このゲームは二人が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で、そのほかの組み合わせはないようです。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>