ペントミノの話題                      戻る

 ペントミノとは、面積 1 の正方形が5個つながった図形で、下図の 8×8 の正方形から
真ん中の正方形(2×2)を除いて得られる12種類をいう。

           

 12種類それぞれには名前が付けられている。(上記図形で適宜、回転、裏返しを施す。)

P 型 L 型 I 型 N 型
T 型 F 型 U 型 V 型
W 型 X 型 Y 型 Z 型

 平成17年3月29日に当HPの掲示板「出会いの泉」に、いつもお世話になっている未菜
実さんから、X 型のペントミノに関して面白い問題の提起があった。

問 題

 n×n (n≧3)のマス目に、x-ペントミノが一つも置けなくなるように穴(1×1)を配置する
とき、穴の最小数を求めよ。

 未菜実さんによれば、    
穴の数 10

とのことである。問題は、n=9 以降について、その規則性はどうなっているだろうか?と
いう疑問である。

 この提起された問題について、当HPがいつもお世話になっている「らすかる」さんがプロ
グラムを実際に組んで、以下のような解を列挙された。(当HPの掲示板より転載)

 掲示板は、時間の経過とともに消え去る運命なので、ここに、未菜実さんとらすかるさん
の研究の成果を書き留めることにした。(未菜実さんとらすかるさんに感謝いたします。)

 以下は、全て最小の解の一つである。

 n=3 のとき、穴の最小数は、 1 n=4 のとき、穴の最小数は、 2
n=5 のとき、穴の最小数は、 3 n=6 のとき、穴の最小数は、 4
n=7 のとき、穴の最小数は、 7 n=8 のとき、穴の最小数は、 10
n=9 のとき、穴の最小数は、 12 n=10 のとき、穴の最小数は、 16
n=11 のとき、穴の最小数は、 20 n=12 のとき、穴の最小数は、 24
n=13 のとき、穴の最小数は、 29 n=14 のとき、穴の最小数は、 35
n=15 のとき、穴の最小数は、 40
n=16 のとき、穴の最小数は、 47

 らすかるさんによれば、n=15 の場合に2時間かかったのを18分で終わるところまで
プログラムを高速化し、n=16 の場合を13時間かけて求められたそうです。私の知らな
い世界で事が運んでいるようで、らすかる様とその愛用のパソコン殿に「お疲れ様!」と
コメントするしかないですね。(n=17 の場合は1ヶ月くらいかかるとのことです...!!)


 らすかるさんからの続報です。(平成24年4月19日付け・・・7年ぶり!)

 私が、2005年にプログラムを作って計算して、n=16までの結果をオンライン整数列大辞
典の「A104519」に新規登録しましたが、久しぶりに見たら、n=29まで拡張されていました。
(私が計算した部分が正しかったことも証明されたことになりますね。)

 そこにURLが載っている論文のPDFを見ると、図も掲載されています。
(最外周を除いた図になっています) すごいですね〜!

(コメント) 確かに感動的!ですね。しかも、アルゴリズムまで...。