テトロミノ 783

2013年08月02日(金)

テトロミノというのは四つの正方形がつながったブロック5種のことをいうわけですが（テトリスのアレと思えば間違いない）それを長方形に敷き詰めていくパズルが中学生のころ「プラパズル」なる商品名でテンヨーから発売されてました。今でも売ってるのかな？

細かいルールなどはこちらを参考にしてください。

5x8のやつは当時既に解の総数がコンピュータで求まってて783通りとありました。それがそのまま商品名でナンバー783という番号が振られていたようです。

コンピュータといってもファミコンがやっと出るか出ないかのころですから、大変だったと思われます。オイラも中学高校のころマイコンで一生懸命解を探してたのを思い出しました。

アルゴリズムとしては簡単です。10個のピースを順番に詰めてくだけ。破綻したら一つ前のをちょっとずらしたり回転したりして・・という枝探索アルゴリズムです。ただ、これだけだと無駄な探索が結構あるんで「空いてる部分の面積が４の倍数でなくなったら破綻とする」という処理をして枝刈をしてました。

面積は再帰的呼び出しを使うと簡単にプログラムでかけるんですがFM7のBASICではそういった処理が難しかったんですよね。さらに当時のBASICで組むとアホみたいに遅い。そこでKコンパイラという工学社から発売されていたコンパイラを使ってプログラムを組んでいました。

今はPCも早いし高速なコンパイラも只で手に入るんで試しにプログラム書いて本当に783種類なのか求めてみました。出てきた解の総数は3106個（ただし回転、反転したものも含む）。この手のパズル。出来た結果をくるっとひっくり返して一致するものは同一とするという暗黙の了解がありますので、その分を按分します。まぁ具体的には1/4にすればいいのですが・・・あれ？4で割りきれない・・・おかすぃ・・・

と思ってたら点対称な解が26個ありました。この分がカウントされてなかった模様。ということで26個足して4で割ると783通り。無事一致しました。ちなみにCore i7で65秒で全解です。いい時代になったもんですねぇ。

ちゅうことで全部の組み合わせリスト

これとは別に5の正方形がつながったペントミノを埋めるほうの全解もほぼ同様のアルゴリズムで求まりますす。こっちのほうは点対称解とかないから簡単。 6x10で2339通り。同じPCで144秒で求まりました。

元祖ワシ的日記