HLAB 2020-2021

ペントミノです。テトリスと似ていますがその名前の通り5個の正方形の組み合わせでできる形（以後「駒」と呼びます）を長方形の盤面にぴったりとはめ込むパズルです。かなり昔、とあるバーで暇そうにしていたらこれの３次元版を出されまして、四苦八苦した記憶があります。もちろん、少々酔いが回っているので^*1解けませんでしたが。

^*15x4x3、6x5x2、10x3x2で立体的に組みます。この記事を書いた今は、しらふなら何とかなったとはもはや思いません（笑）。

このペントミノ、簡単そうに見えて難しいです。盤面の形によっては何千もの解があるくせに、なかなかその一つにたどり着けません。これをPrologで解くというのが今回のテーマです。

丸数字は解の得られた順番。８個ありますが、点線で線対称になっています。

（全部読むには 全文表示 をクリックしてください。）

駒は12種類あり、それを一つずつ組み合わせて長方形を作ります。基本となる正方形の数は次の式で計算できます。

（駒一つあたりの正方形の数： 5）　×　（駒の数： 12）　＝　（盤面の面積： 60）

　面積が60になる長方形は、1×60、2×30、3×20、4×15、5×12、6×10の6種類ありますが、駒一つの見つけの大きさが3×3になるものもあるので最初の二つはどうやっても配置できませんので除外されます。したがって3×20、4×15、5×12、6×10の四種類の盤面で配置を考えることになります。

Wikipediaには、6×10の盤面の場合で2,339個も解があるとあります。それだけあれば解の一つぐらいすぐにも見つかりそうなものですが、駒は全部で12個もあるので探索木のサイズは尋常ではありません。プログラムを書くときにはこの探索木の無意味な枝をどうやってカットするかが課題になるでしょう。

下のプログラムは例のごとく直感的に書いてあるので非常に遅いです。たぶんこのままでは一つ目の解を得るだけで何日か掛かるのではないでしょうか。解は得られませんが、このままでもパズルを解いている様子は観察できます。数十分程度で解が欲しい場合はコード中コメントアウトされているkinsoku_checkを実装してみてください。

禁則ルールにはいろいろ候補があると思いますが「各駒を配置した後の空きグリッド（正方形）のクラスタに5の倍数でないものがあってはならない」を実装してこの記事の解答例を作りました。空きクラスタが５の倍数でなくなってしまうと、それ以降、その空きクラスタをきれいに埋められる駒の組み合わせは存在しないことを利用しています。駒はすべて5個の正方形からできていますから。

3×10の場合をこのプログラムで解いたところ8個の解が得られましたが、1枚目の図（上）を見ての通り水平鉛直に対称になっているのでこの盤面での実質的な解の数は2です。2枚目の図（下）は、6×10の盤面でプログラムを流しっぱなしにしたときの複数解の例です。1920x1200のディスプレイに並べられるだけ並べてダンプを取りました。対称性は考慮していないので重なりはあると思います。放置しておけばたぶん9,356個の解が得られただろうと想像します。もちろん確かめていません。

■■■■■の駒（I）*2を外した5×11の変形ペントミノの動画

（コーデックはH264です。再生出来ない場合はffdshow-tryoutsをインストールしましょう。）

^*2ペントミノの駒には名前がついており、それぞれF、I、L、N、P、T、U、V、W、X、Y、Zになります。

さて、これがどのように建築に応用できるかですが、平面の自動設計のアルゴリズムに使えるような気がします。

コードは後日掲載します