ページ内リンク
ヘキソミノ： 分割方法、組み合わせ順序、
パーツ・リスト
ペントミノ： ４分割パーツ・リスト、２分割パーツ・リスト、パーツ・リスト考察
Version History：
自分でも当然検証を進めていきますが、ちょいと心配です。どなたか、追試、検証をしていただけませんでしょうか？ご意見、ご質問等お待ちしてます。（メールでも、掲示板でも結構です。）
ヘキソミノの場合 to Top
分割方法
ヘキソミノは、完全な長方形でない為、上下対称ではありません。パーツ分割する時に、
この部分をどう扱うかが、効率化の一つの鍵になるかと思います。
 |
左図で、黄色の部分は、セルのJ1とJ12にさまざまなピースを置いた時に埋まる可能性のある領域です。 その部分を境界にし、同型を４個切り出すことを考えると、①②③の３種類のパーツ・リストが必要になります。これをベースにいろいろ検討をしたのですが、②と③に共通する部分が多いことと、①の形状が面積に対して境界線が長いため、インデックスの階層がより深くなることが不利になるように思われます。 |
 |
今現在、検討しているのは、この方法です。本来、上側と下側は形状が異なるので、別々のパーツ・リストが必要になるのですが、途中までは全く同じですので、後半部分だけ２つのパターンについて探索を行い枝分岐の中で合わせて分類、管理すればよいように思われます。 これをベースに、より小さいパーツに分割するかどうかは、後ほど改めて検討しようと思います。 |
ここからは、中村さんのサイトにあった、左のサンプルを使って検討を進めようと思います。
上の分割方法に従うと、このサンプルは、以下の４つのパーツから構成されていることになります。
|
 |
||
 |
|
パーツ細分化
やはり４分割では、規模がまだ大きく、探索にかなりの時間がかかってしまうことが予想されるので、さらなる細分化を検討してみます。
いろいろな形状を検討したところ、中央上部を除くと、それ以外の部分は、a と b のパーツの組み合わせで作ることができます。細長い形状は、インデックス化に不利にも思えますが、なるべくパーツの種類を少なくするという観点からはメリットがありそうです。a も b の一部なのですが、とりあえず別パーツとして扱う方がシンプルに思えます。（大した根拠はないので、再考の予定）
上のサンプルから抜き出すと以下のようなパーツになります。
右上部分も左右反転させて、以下のようになります。
中央部分は、J1の出っ張りを埋めているピースが左側にどれだけ伸びているかによって、パーツの幅を変える必要があります。
 |
 |
これらの特性を考慮に入れると、以下の３種８分割が、ちょうど良いように思われます。
だいぶ話が込み入ってきたので、整理する上でも、次回は、パーツ・リストから解を求めていく流れをまとめてみようと思います。
組み合わせ順序 to Top
４つのパーツの組み合わせ方として、
－１．左の２つを組み合わせ、２分割パーツ・リストを作成してから、左右を合わせる
－２．左の２つを組み合わせ、それに右上のパーツ、最後に右下のパーツを合わせる
パーツ作成と同時に解が求まっていくことがモチベーションの維持に有効
パーツを階層化する場合でも、単にサブ・パーツを延々準備するのはつまらない。
というあたりを考慮して、－２．で進めてみる。
パーツ・リスト to Top
まず、境界上に並ぶピースを順に、それぞれピース番号、向き、上下位置の３つを定義して行きます。
この例では、
を 
の向きで、
５段目の位置に置くという情報になります。
３５ピースの定義に６ビット、最大８通りの向きに３ビット、最大６段の位置に３ビットで、合計１２ビット必要になります。
横方向の境界が１０マスですので、最大で１０ピースが使われる可能性があります。上の例では右下のパーツが９ピースを使用。１ピースの１２ビットなので、横方向だけで１２ｘ１０＝１２０ビットになります。
縦方向の境界は残り５マスで、１２ｘ５＝６０ビット、３５ピースのどれが、パーツに使用されているか、いないかにそれぞれ１bitで表現して３５ビット、これらのトータル２１５ビットで１パーツが定義できます。形状情報がすべて境界上のピース並びに包含されるので、かなりコンパクトになります。
実際にパーツ・リストから検索して使う時には、使用しているピースが同じで、境界上のピースも同じだけれど、それ以外のピースの置き方が異なるものについては一括して処理できるので、その個数を保存する領域が必要になります。その数がどのくらいになるかは、よくわからないので、まずは、パーツ・リストをフラットに作成し、インデックス化する時に再検討することになるかと思います。
この部分、文章ではわかりにくいので、図示化をそのうちに・・・
