新・身近な科学

私たちの身近にある科学を解説します。NSI (科学勉強会) のウェブサイトはこちら http://tehiro.sakura.ne.jp/nsi/

ポリオミノ

※本記事はアドベントカレンダー「明日話したくなる科学豆知識4」(http://www.adventar.org/calendars/1675)の一環として書いています。


こんにちは。NSIの小川です。

NSI(科学勉強会)では,時折,有志のメンバーでリアル脱出ゲームというイベントに参加して遊んでいます。リアル脱出ゲームとは,名前のとおり,始めに実際に部屋等に閉じ込められ,参加者で協力して謎を解いて脱出を目指す,体験型イベントです。

さて,こういったイベントに参加すると,よく以下のような「正方形をいくつか組み合わせた形のピースを複数用いて,枠内(多くの場合は長方形)に収めるパズル」に出くわし,苦しめられることがあります。
f:id:nsi_sapporo:20161216085006j:plain

このパズルについて,何か攻略法はないだろうかと調べていくうちに,このパズルが「ポリオミノ」と呼ばれており,思っていたよりも奥が深いものであることが分かったので,今日はこの「ポリオミノ」についてご紹介します。

古くからパズルとして全世界で親しまれてきました「ポリオミノ」ですが,初めてこの語が用いられたのは,数学者ソロモン・W・ゴロムが,1954年に発表した論文「Checker Boards and Polyominoes」だと言われています。

彼は,接頭語「poly」と「omino」(ドミノdomino=di(2)+ominoから)を組み合わせて「polyomino」との造語を考案,n個の正方形をつなげた形をn-オミノ(nにはギリシア語の接頭辞が入る)と呼びました。

ここでテトリスを想像してください。あれは,正方形を4つつなげたn=4の「テトロミノ(tetra=4)」ということが出来ます。では,テトロミノは何種類存在するのでしょうか?(裏返すと同じ形になるものは1種類とカウントします。)

答えは5種類です。
f:id:nsi_sapporo:20161216085010j:plain

では,ペントミノ(penta=5)はどうでしょう?

答えは12種類です。このあたりまでなら,まだイメージも付きますが,以下,ヘキソミノ(hexa=6)35種類,ヘプトミノ(hepta=7)108種類,・・・と加速度的に増えていき,n=10では1285種類,n=15では100万種類近くなります。2015年時点ではn=45の場合の種類数まで計算が進んでいるようですが*1,研究の対象となって60年以上経過した現在でも,その法則性については未だ明らかになっていないようです。

私が一番面白いと思ったのは,ペントミノ(面積5)12種類の全てを使って,面積60の長方形すべて(6×10,5×12,4×15,3×20)*2にぴったりと収めることが出来るそうです。なお,6×10の長方形には2339通りの収め方があるのに対し,3×20の長方形には2通りの方法でしか収めることはできないそうですので,皆さんぜひ考えてみてください。

以上,今日の「明日話したくなる科学豆知識」はポリオミノは,数学的研究対象にもなっているが、その法則性は未だに明らかになっていない」でした。

ところで個人的に一番知りたかった攻略法については,コンピュータ解析は進んでいるようですが,リアル脱出ゲームの際に自力で使えそうなものは見つけることが出来ませんでした。やはり習うより慣れろということなんでしょうか。

*1:「ガードナーの数学パズル・ゲーム」,マーティン・ガードナー著,日本評論社,2015

*2:最大辺の長さが3のペントミノがあるため,2×30,1×60は当然除外しています