読者です 読者をやめる 読者になる 読者になる

みたにっき@はてな

三谷純のブログ

BurrTools と 24パズル

先日の折紙のイベントで、前川さんの24パズルが話題に出て盛り上がっていました。
(折紙好きとパズル好きは、かなり共通点があるようです)


この24パズルは、4角形の4辺に「凹・凸・平ら」を割り当てると、異なる24種類のピースを作ることができて、それがちょうど長方形の枠に収まる。というものです。
詳しくは、前川さんのブログ参照。


■ 24パズル | 前川淳 折り紙&かたち散歩
http://origami.asablo.jp/blog/2010/12/01/5550455


このパズルの解の数(ピースの表と裏に違う色が付いているので、同じ色が見えるように枠内に収める方法)については、今から4年前に議論していて、BurrTools と 自前のプログラムで、295,856通りであることがわかっています。

詳しくは次のエントリ参照
http://d.hatena.ne.jp/JunMitani/20101223


ただし、この時の数え上げでは、180度回転させて一致する場合も別解としてカウントしていたので、
これを同一であるとみなせば(当然、同一とみなすべきですが)、その場合は半分の147,928通りになります。


さて、このパズルについて、イベントの時に、次のようなチェッカー模様に敷き詰める例を前川さんが示してくれました。


で、疑問に思ったのが、このようなチェッカー模様に敷き詰められる解は何通りあるだろうか。ということ。


さっそく、自前のプログラムで確認したところ、先ほどの場合よりも多い数になってしまいました。
おかしいなぁ、と思って、BurrToolsでも確認(下図)。



その結果は「403,508通り」となって、やはり、大きな数字になりました。
つまり、全面を茶色で枠に収める一般的な問題よりも、チェッカー模様に敷き詰める問題の方が解が多いということ。


よくよく考えてみると、チェッカー模様に敷き詰める問題は、どのピースを表(茶色)にして、どのピースを裏(白色)にするかという選択の自由(24ピースから12のピースを選ぶ場合の数)があるので、解の数が増えるのかなと思いました。


解の数が多い=簡単、というわけではなくて、(解の数)/(場合の数)が小さいほど難易度が高いと考えると、やはりチェッカー模様の方が難易度が高そうです。


ちなみに、『外枠に接する16ピースは茶色、それ以外の8ピースは白色』という制約の場合は、全部を茶色にする問題と同じだけの解の数があるという興味深い結果が得られました。


奥が深いです。