Hatena::ブログ(Diary)

小人さんの妄想 このページをアンテナに追加 RSSフィード Twitter

2010-12-13

ウソつきっ娘論理プログラミング

全ての問題にかわいい女の子が出てくる、「登場する人物の発言を手がかりに問題を解くタイプ」の論理パズル集。

萌え萌えウソつきッ娘論理パズルI

萌え萌えウソつきッ娘論理パズルI

* 出版社での紹介 >> http://www.tp-ep.co.jp/ep-hp/top.html

第1問目は、こんな感じです。

* 第1問目の画像イメージ >> http://www.tp-ep.co.jp/ep-hp/images/top/ronripazuru_01.jpg

【Q1】水泳大会

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

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

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

 ことり「私は1位」

 なる 「私はすずより上位」

 すず 「私は1位か2位」

 あゆ 「私は1位か2位」

こういった問題が全部で60問出てきます。

試しに何問かやってみるとわかるのですが、この手の問題にはある程度パターンがあって、

コツさえ掴めれば、後はほとんど機械的に解けます。

・・・だったら、機械に解かせるべきではないか。

そう思って、まずこの第1問目をパソコンで解いてみることにしました。


実は、パソコンにはこういった論理パズルを解くためのプログラミング言語があります。

Prologです。

いくつかあるProlog実装のうち、今回は SWI-Prolog というものを使ってみました。

* SWI-Prolog's home >> http://www.swi-prolog.org/

Prolog言語自体については、こちらのページが参考になります。

* お気楽 Prolog プログラミング入門

>> http://www.geocities.jp/m_hiroi/prolog/


インストール時の注意点(Windows版)

※ もし Perl を使っていたのなら、拡張子に注意が必要です。

※ SWI-Prologデフォルト拡張子は「.pl」となっており、Perl拡張子と重複します。

※ このため、インストーラーでは「.pl」の代わりに「.pro」も選べるようになっています。

※ 私は「.pl」にも「.pro」にもせずに、以下の説明に従って拡張子を「.swi」に設定しました。

インストーラ拡張子を設定する項目がありますが、説明を読むと .PL と .PRO では不都合があるようなので、おススメされていた .SWI としました。

これで SWI ファイルをダブルクリックすると、SWI-Prolog を起動してプログラムが実行されます。

-- http://www.geocities.jp/m_hiroi/prolog/#SWI より.

さて、インストール後、最初に悩むのは「どこにプログラムを書けばいいの?」ということです。

以下に、やり方を書いておきます。


1.拡張子が.swi(人によっては.pl)という空のファイルを作成します。

  例えば "test.swi" といった名前の空ファイルを作成します。

2..swiファイルをダブルクリックすると、SWI-Prologが起動します。

  ?- が入力プロンプトで、ここにPrologへの「問い合わせ」を入力することになります。

f:id:rikunora:20101213082721p:image

  もし最初の.swiファイルにプログラムが記述してあれば、起動時にそのプログラムが読み込まれます。

  しかし今回は空のファイルから起動したので、何も読み込まれていません。

3.メニューの [File] -> [Navigator...] を選択すると、Prolog Navigator ウィンドウが現れます。

f:id:rikunora:20101213082752p:image

4.ナビゲーター上では、最初に起動した.swiファイルが緑色に表示されています。

  この緑色になっている.swiファイルを選択して、[右クリック] -> [Edit]、

  またはメニューにある鉛筆アイコンのボタンを押すと、編集画面が立ち上がります。

  プログラムは、この編集画面に書き込むことになります。

f:id:rikunora:20101213082819p:image

5.編集画面の使い方は、普通のテキストエディタと同じです。

  ここにプログラムを書き込んだら、メニューの [File] -> [Save Buffer] で内容を保存します。

  実のところ、この編集画面は単なるテキストエディタなので、

  別のテキストエディタで直接.swiファイルを編集してもかまいません。

6..swiファイルの編集を終えたら、最初に開いたPrologのメインウィンドウに戻って、

  メニューの [File] -> [Reload Modified Files] を選択すると、

  変更のあった.swiファイルの読み込み直しが行われます。

7.以上のようにして、「.swiファイルの編集」->「読み込み直し」を繰り返して、

  プログラミングを進めることになります。

8.Prologプログラムを読み込むことを「Consult」といいます。

  メニューの [File] -> [Consult...] から直接プログラムを読み込むこともできます。

  また、入力プロンプトから、

   ?- ['c:/MyWork/Prolog/test.swi'].

  とファイル名を入力することで、プログラムを読み込むこともできます。

  (入力の最後にあるピリオド . を忘れずに!)


さて、当初の水泳大会の問題に戻りましょう。

まず最初に、登場する4人の女の子の全ての並び順(順列)を表示してみましょう。

.swiファイルに、次のプログラムを入力して、読み込み直しを行ってください。

moemoe_swimming(X) :-

permutation([kotori, naru, suzu, ayu], X).

f:id:rikunora:20101213082850p:image

permutation とは順列のことです。(permutation という表記は SWI-Prolog独自のものです)

Prologでは値の並びのことを「リスト」といって、[a, b, c] といった書き方をします。

そして、メインウィンドウの ?- プロンプトに、

moemoe_swimming(X).

と入力します。

f:id:rikunora:20101213082915p:image

女の子の並び順が、まず最初に1行だけ表示されます。

1行表示されたところでセミコロン ; を入力すると、2行目に次の並び順が表示されます。

セミコロン ; を次々に入力すると、全24通りの順列がなくなるまで表示が続きます。

途中でイヤになったら、ピリオド . か、リターンキーを入力すると、表示はそこで中断します。


次に、

 ことり「私は1位」

という条件をプログラムに付け加えてみます。

プログラムを次のように書き換えて、読み込み直しを行ってみます。

moemoe_swimming(X) :-

permutation([kotori, naru, suzu, ayu], X),

nth1(1, X, kotori).

nth1(1, X, kotori) というのは、「X の 1 番目に kotori がある」という意味です。

(nth1 という表記は SWI-Prolog 独自のものです)

Prologでは、カンマ , 区切りで文章を付け加えると、AND条件として加わります。

また、セミコロンで ; 区切りで文章を付け加えると、OR条件として加わります。

(入力プロンプトで入力した ; セミコロンは、「また次の答は」という意味だったのです。)

メインウィンドウの ?- プロンプトに、先ほどと同じように moemoe_swimming(X). と入力すると、

今度は、ことりが一位になっている順列だけが表示されます。

?- moemoe_swimming(X).

X = [kotori, naru, suzu, ayu] ;

X = [kotori, suzu, naru, ayu] ;

X = [kotori, suzu, ayu, naru] ;

X = [kotori, naru, ayu, suzu] ;

X = [kotori, ayu, naru, suzu] ;

X = [kotori, ayu, suzu, naru] ;

false.

次の、

 なる 「私はすずより上位」

という条件を入れるには、次のようにします。

naru_faster_suzu(L) :-

nth1(Idx1, L, naru), nth1(Idx2, L, suzu), Idx1 < Idx2.

moemoe_swimming(X) :-

permutation([kotori, naru, suzu, ayu], X),

nth1(1, X, kotori),

naru_faster_suzu(X).

nth1(Idx1, L, naru) というところは、「L の中の Idx1 番目に naru がある」という意味です。

naru_faster_suzu(L) は、

「L の中に naru がある位置と、L の中に suzu がある位置を比べると、naruの方が小さい」ということです。

ここまでの条件にあてはまるものは、以下の3つだけになりました。

?- moemoe_swimming(X).

X = [kotori, naru, suzu, ayu] ;

X = [kotori, naru, ayu, suzu] ;

X = [kotori, ayu, naru, suzu] ;

false.

さらに、残る2人の条件も入れてしまいましょう。

 すず 「私は1位か2位」

 あゆ 「私は1位か2位」

naru_faster_suzu(L) :-

nth1(Idx1, L, naru), nth1(Idx2, L, suzu), Idx1 < Idx2.

moemoe_swimming(X) :-

permutation([kotori, naru, suzu, ayu], X),

nth1(1, X, kotori),

naru_faster_suzu(X),

( nth1(1, X, suzu); nth1(2, X, suzu) ),

( nth1(1, X, ayu); nth1(2, X, ayu) ).

ここまで4人分の条件を入れ込むと、あてはまる結果は1つも無くなります。

?- moemoe_swimming(X).

false.

4人のうち、誰か一人がウソをついているということです。

順番に調べてみましょう。

まず、ことりがウソをついているとして、ことりの条件のところを not( ) で囲ってみます。

naru_faster_suzu(L) :-

nth1(Idx1, L, naru), nth1(Idx2, L, suzu), Idx1 < Idx2.

moemoe_swimming(X) :-

permutation([kotori, naru, suzu, ayu], X),

not( nth1(1, X, kotori) ),

naru_faster_suzu(X),

( nth1(1, X, suzu); nth1(2, X, suzu) ),

( nth1(1, X, ayu); nth1(2, X, ayu) ).

結果、やはりあてはまるものがありません。

似たようなやり方で、なるがウソをついていたとすると、

・・・やはり結果なし。

続いて、すずがウソをついていたとすると、

naru_faster_suzu(L) :-

nth1(Idx1, L, naru), nth1(Idx2, L, suzu), Idx1 < Idx2.

moemoe_swimming(X) :-

permutation([kotori, naru, suzu, ayu], X),

nth1(1, X, kotori),

naru_faster_suzu(X),

not( nth1(1, X, suzu); nth1(2, X, suzu) ),

( nth1(1, X, ayu); nth1(2, X, ayu) ).

結果が1つだけ出てきました。

?- moemoe_swimming(X).

X = [kotori, ayu, naru, suzu] ;

false.

つまり、これが答ということですね。

ついでに、最後のあゆがウソをついていたとしても、やはり結果は出てきません。

ということで、答はさっきの1通りしか無いことが確かめられました。


ひとくちにプログラミング言語といっても、Prologは他の言語とはかなり毛色が違っています。

定型プログラムを完成させるというより、対話しながら論理を探ってゆくためのものです。

どちらかと言えばデータベースに問い合わせるSQL言語に近い感じ。

あと、言うまでもないことですが、この本に着目したのは純粋に論理パズルを楽しむためであって、

決してイラストにつられてフラフラと手にとってしまったわけではありません!


せいたかのっぽせいたかのっぽ 2010/12/13 19:24 論理パズルって、論理的に順を追って考えていけば、答えを確認しなくても、必ず確信のもてる解答にたどり着けるところがスッキリした気分になりますよね。
むしろ、必ず答えが一つ、論理的に他の解答が無いような問題を作る作者の方がずっと大変かも。
ブルーバックスでも同じ作者から、
「迷いの森」のパズル魔王に挑戦!
というのが出てて、そちらを最近ちょうど私も買ったばかりだったのでコメントしました。
あと、言うまでもないことですが、私の場合は表紙のイラストにつられて買ってしまいました(笑)。

rikunorarikunora 2010/12/14 13:23 論理パズルは解く人も悩むけれど、それ以上に「他の解答が無いような問題を作る」のが一番大変なのだと思います。
たぶん作者は全部のパターンをチェックするでしょうし、ひょっとするとパソコンでチェックしているかもしれません。
あと、言うまでもないことですが、上の記事には1つウソが混じっています!

せいたかのっぽせいたかのっぽ 2010/12/14 19:42 上の記事の1つのウソについては、論理的に考えない方が、
同・感・・・という感じです。(^-^)/

三毛公爵三毛公爵 2010/12/15 04:31 ここに書いてあるプログラムとほぼ同じ思考方法で答えを出しました。唯一の答えが出るというのはとてもキモチがいいです。

でもこれは順位が決まったりするものすごい具体的なものには強いですが、抽象的なものの推理には弱そうな気がします。やはり仰られているようにデーターベースの総検索的なイメージですね。もしも抽象的な意味理解や推察ができたら国会にでも置いて、「ここがおかしい」と言わせてみたいです。でも解なしの場合はループしそうで怖いですね。

話は変わりますが私も最近買った本にこんなものがありまして

http://p.tl/-viB(amazon 書籍:CPUの創り方)

最近は買う本の表紙が萌え絵になってることが多い様に感じます。流行?それとも趣味が同じ人はこういうものが好き?かと疑問に思ってしまいます。でも実物を見ると少しうれしかったりします。

rikunorarikunora 2010/12/15 11:05 趣味が合いますね〜、CPUの創り方、実は持ってたりして (^_^;)
つまり、我々が買ってしまう限り、この手の本が増えてゆくということなわけで。。。

もし抽象的なものの推理がプログラムできたなら、人間に代わってコンピュータが判決を下すようになるのではないでしょうか。
そうなると、いよいよ人間はモノを考えなくなるかもしれない。
新憲法 2.0は 数式で >> http://d.hatena.ne.jp/rikunora/20081224/

小屋畑 拓小屋畑 拓 2015/10/13 14:34 面白そうだったので私も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.


実行結果:
[1] 4 ?- girl_order.
[1,3,4,2][1,1,0,1]
true ;
false.

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

この問題面白かったので自分のページでも掲載したいのですがリンク貼っても良いでしょうか?
(http://www2.koyahatataku.com/)

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/rikunora/20101213/p1