Yペントミノ
|
中公新書「数理パズル」池野信一(他)著の中に、同形のコマを使用した箱詰め問題が紹介されていました。 そこからYペントミノを用いたものをいくつか拾い出して解いてみることにします。Yペントミノは下図のように8種の形状をとり得ます。 |
|
同書に『素な長方形』という概念が示されています。『素な長方形』とは、同じ駒で作られる小さい長方形を組み合わせて作りあげることのできない、長方形のこととされています。駒を詰めることが可能な、ある大きさの長方形が、それより小さい長方形で分割できるのであれば、それは「素な長方形」ではありません。 以下で課題としてとりあげたYペントミノ同形箱詰め盤は、もちろん『素な長方形』になっています。 |
|
javaで求解 |
（1）5×10盤-----コマ数10
 長方形を作れる最小のコマ数です。解は人手によってもすぐに 求められることでしょう。左右対称、上下対称、180度回転対称になる解を除いた 独立解は4個です。 |
|
javaで求解 |
（2）10×14盤-----コマ数28
コンピュータならすぐに解が出てきます。独立解は79個です。 |
|
javaで求解 |
（3）11×20盤-----コマ数44
 1分以内に解が出ます。独立解は44個です。 |
|
javaで求解 |
（4）15×15盤-----コマ数45
盤が正方形ですから90度回転したものも対称解になります。 |
|
javaで求解 |
（5）9×30盤-----コマ数54
 最も長細い盤です。みるみるうちに解が出てきます。3115個 |
|
javaで求解 |
（6）11×30盤-----コマ数66
 この盤も最初の解は数秒で出てきますが、解の数が6018と多数なので、全部を探索するには6743秒かかりました。(CPU:400MHz) |
|
javaで求解 |
（7）22×25盤-----コマ数110
最初の解を出すのに32時間費やしました(CPU:400MHz) |