小学生新聞の論理パズルをPrologで解く
Description
息子が来年から小学生ということで、妻の強い要望によって10月から小学生新聞をとるようになった。
最初は「令和にもなって新聞！？」なんて思っていたんだけど、いざ購読してみると毎日の食事の話題に不自由しなくなった。時事は勿論のこと、算数や理科や芸術など内容は多岐にわたっていて、子どもの興味を引く工夫が見られる。それにもかかわらず、一部あたり100円未満なので、とても経済的だ。
さて、先日の新聞は４面がパズルだった！
「5歳児にはちょっと早いかな。」
なんて言って、親だけしっかりと楽しんだ笑
問題のうち、二問は以下に示すような推理パズル――いわゆる、Zebra Puzzleですな――だった。
問題
３人が折り紙を折りました。３人の会話から、だれが何を折ったか推理しましょう。
・それぞれ折った作品と色はちがいます。
・自分のことを他人のことのように言っている人はいません。
３人の会話
・相田「緑色のツルを折った人がいます」
・飯田「青い折り紙を使って折りました」
・上田「相田さんは花を折りました」
-- 朝日小学生新聞 2024年10月13日 第18600号
このほかに表から分かる情報をまとめると次のようになる。カブトは一切言及されていないけど解けることに注意。
名前
- 相田
- 飯田
- 上田
作品
- ツル
- カブト
- 花
色
- 赤
- 青
- 緑
二問目がこちら。
問題
絵画クラブのみどりさんは７月から１０月にかけて、１か月に１枚合計４枚の絵をかきました。何月にどんな画材を使って何を題材にかいたのか当ててください。使った画材とかいた題材はそれぞれちがいました。
みどり「７月には人物画をかきました。色鉛筆では風景画をかきましたが、それは１０月ではありません。クレヨンは９月にも１０月にも使っていません。油絵の具を使ったのは８月ではなく、また油絵の具では動物はかいていません。水彩絵の具を使った次の月に、油絵の具を使いました。」
-- 朝日小学生新聞 2024年10月13日 第18600号
このほかに表から分かる情報をまとめると次のようになる。こちらも、果物について一切言及されていないが問題なく解ける。
時期
- 7月
- 8月
- 9月
- 10月
画材
- クレヨン
- 色鉛筆
- 水彩絵の具
- 油絵の具
題材
- 人物
- 風景
- 果物
- 動物
これらはちょっと工夫すれば紙と鉛筆で解くことができる。今回は暇つぶしにPrologを使って解いてみた。
Prologはその名前の由来（PROgramming in LOGics）が示すように、論理に根ざしたプログラミング言語だ。事実と規則を記述して、質問を投げれば回答が得られる。というのが大まかな仕組みだ。このような問題はまさにPrologの出番というわけ。
最初の問題に対応するプログラムは次のとおりだ。
contains_all([First|Rest], Lis) :- member(First, Lis), contains_all(Rest, Lis).
contains_all([], _).
solve1(A) :-
[[A11, A12, A13], [A21, A22, A23], [A31, A32, A33]] = A,
[A11, A21, A31] = [aida, iida, ueda],
contains_all([crane, helmet, flower], [A12, A22, A32]),
contains_all([red, blue, green], [A13, A23, A33]),
member([aida, flower, _], A),
member([_, crane, green], A),
member([iida, _, blue], A).
これは補助的な述語contains_allと、問題を解くための述語solve1だけからなる。
大前提として、Prologでは大文字から始まる識別子は変数として扱われる。solve1は引数Aが後述するすべての条件を満たすか判定する述語である。Prologの述語には変数を与える事ができて、その場合はPrologは条件を満たす解をすべて表示してくれる。したがって、solve1に問題の条件を適切に記述できればPrologがその答えを導いてくれる。
問題の解を二次のリスト——行列だと思っていてよい——で表現する。
[[A11, A12, A13], [A21, A22, A23], [A31, A32, A33]] = A,
このとき、名前の列は勝手に定めてよいので次のようにできる。
[A11, A21, A31] = [aida, iida, ueda],
次のように書いてもよかったね。
[[aida, A12, A13], [iida, A22, A23], [ueda, A32, A33]] = A,
作品と色は、それぞれ一回だけ出現するという条件を次のように表現する。
contains_all([crane, helmet, flower], [A12, A22, A32]),
contains_all([red, blue, green], [A13, A23, A33]),
ここで使用されているcontains_allは第一引数のリストのすべての要素が第二引数のリストの要素である場合に真を返す述語だ。第一引数が第二引数のリストの要素だった場合に真を返す、組込みの述語memberを用いて再帰的に定義してある。
contains_all([First|Rest], Lis) :- member(First, Lis), contains_all(Rest, Lis).
contains_all([], _).
最後に、会話を条件として組み込む。ほとんど問題文と対応していることが分かるだろう。
member([aida, flower, _], A),
member([_, crane, green], A),
member([iida, _, blue], A).
今回作ったプログラムを実行するには次のようにする。
$ swipl -f solver.pl
Welcome to SWI-Prolog (threaded, 64 bits, version 9.3.12-61-g8ee3600c7)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.
For online help and background, visit https://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).
1 ?- solve1(X).
X = [[aida, flower, red], [iida, helmet, blue], [ueda, crane, green]] .
2 ?- solve2(X).
X = [[july, portrait, crayons], [august, scenery, colored_pencils], [september, animal, watercolors], [october, fruit, oil_paint]] .
3 ?- halt.
solve1の結果は次のように解釈できる。
相田: 赤色の花
飯田: 青色のカブト
上田: 緑色のツル
二問目もちゃんと解けてるね！
7月, 人物画, クレヨン
8月, 風景画, 色鉛筆
9月, 動物, 水彩絵の具
10月, フルーツ, 油絵の具