スライドパズルのはなし。(2 of 3)
2012-10-15Mathematics
では、前回の問題の答えです。
問題は次のとおりでした。
この問題は、実はとても有名な問題で、サム・ロイドの「14-15パズル」と呼ばれるものです。サム・ロイドはアメリカのパズル作家で、1878年にこの問題を考案したそうです。
この問題には賞金がかけられていたのですが、ついにその賞金を手にした人は現れなかったそうです。
なぜか。それは、14と15を入れ替えただけの状態には、どのようにスライドさせてもできないからです。サム・ロイドは、不可能であることを分かった上で、話題作りのためにこの問題を考えたのですね。なぜ不可能であるか、その簡単な説明を、このエントリーの最後に掲載したいと思います。
さて、スライドパズルのネタの2本目です。次の絵を見てください。
太陽の顔を真ん中のところに入れなさい、というのがこの問題の趣旨です。面白いことに、これはもしかしたら人間なら解けるかもしれませんが、あることに気づかないとコンピュータさんに解いてもらおうと思っても解けないかもしれません…。
この問題については、先にその出典を示します。このパズルはJ.I.Wileyという人が、1914年にが”Get My Goat”という名前で考案したものが下敷きになっていて、これを日本の著名なパズル作家である芦ヶ原伸之がアレンジしたものを、私がトレースし直したものです。パズル自体はもう、90年も前のものなのですね。
この問題の答え…というか、何がポイントなのかは、次回ご紹介いたします。
サム・ロイドの14-15パズルの簡単な説明。
下の図を御覧ください。
パネルの並びを数列で表して、その並びを観察しています。並びが変わらない動かし方と、変わる動かし方があるのですが、並びの変わる動かし方は、必ず偶数回入れ替えを行うことが分かっています(なぜ偶数回かのこの説明は省略します)。スライドパズルの操作でできることは “偶数回の入れ替えによって出来る状態にすること” なのに対して、14と15だけを入れ替えるという操作は、1回の入れ替え、つまり奇数回の入れ替えとなるわけですから、どう動かしても、奇数回の入れ替えによって出来る状態にすることはできません。
この説明は、http://homepage2.nifty.com/TOMOMI/text/14-15.pdf こちらの説明を元にいたしました。
Topic
- Mathematics (15)
- Natural Language Processing (1)