部分解への分割方法の検討 | ||||||
ver.0.11 2010/01/28 daichinあっとexcite.co.jp | ||||||
http://hexomino.hp.infoseek.co.jp/ | ||||||
・Version History |
||||||
自分でも当然検証を進めていきますが、ちょいと心配です。どなたか、追試、検証をしていただけませんでしょうか?ご意見、ご質問等お待ちしてます。(メールでも、掲示板でも結構です。) |
||||||
ペントミノの場合
|
それではということで、各パーツに対して、数手先までチェックし、解の無いものを枝刈りしたり、せっかく探索するので、その結果をデータとして保存し、その後の探索に利用するとか、いろいろ試してみたのですが、結果として高速化に繋がるような有効なアイデアが見つからず、・・・・フェードアウトしてました。
ということで、長い前置きがやっと終わって、ここからが今回のアイデアです。
ペントミノは全体が6x10マスなので、左図のように3x5の領域に4分割できます。 | |
この図6の薄緑色の領域を埋めるというのを条件にすると、左図の例のようになります。当然ですが、他の領域にはみ出してしまいますが、これでいいんです。この条件のパーツをすべて求めると、それ以上ピースの探索は一切必要ない(のではないか)というのが今回の最大のポイントです。 | |
では、図7の灰色の残りの部分を
どうやって埋めるかなんですが、はみ出しているピースだけを残して、上下反転させると、左図になります。そうなんです、このパターンを含んだパーツは、上で求めたパーツリストの中にすでに存在するのです。 それを見つけてくるのは、「探索」ではなく、「検索」になるというのはわかりますでしょうか? |
パーツ・リストの考察
これらのパーツを分類し、検索できるようにし、かつサイズの小さいパーツ・リストを設計する必要があります。 それぞれのピースに対しては、形状、向きに加えて、上下位置を情報として持つ必要があります。上下位置は、左上からとかルールに従って順に詰める場合には必要ありませんでしたが、パーツ・リストの場合、形状と向きは 図8と同じでも、左図のように別の並べ方が存在するためです。 |
ペントミノの場合、12ピースを区別するのに4bit、向きはピースによって異なり、最大で8通りで3bit、上下位置は3通りで2bitになり、1ピースに9bit必要になります。 (2001年のnakaさんとのやり取り)
図7の例では、6ピースが、図6の薄緑色の長方形領域の境界に使われているので、境界を定義するのに、9bit x 6ピース = 54bitが必要になります。
境界が7コマなので、最大では、7ピースになる可能性があります。適当に手で並べて見たのが左図ですが、これは、この先行き詰まるのが分かります。 (十字を置くところがない) プログラムを作れば簡単に検証できるのですが、まとまった時間が取れず、しばらくは紙の上での思考を続けます。 | |
図7の例では、すべてのピースが境界に絡んでいるのですが、
下側になる図8の場合は、左図のように境界に絡むのは、4ピースで、絡まないピースが一つあります。(左上、水色のピース) パーツを組み合わせる時には、境界のピース以外が重複していない組み合わせを検索できるようにする必要があります。 |
|
また、左図のように、はみ出しが無い場合もあり、境界領域のインデックスを1列ではなく、2列にする必要がありそうです。 これは、ペントミノの全体が6x10と、縦横とも偶数なためで、ヘキソミノは11x19と、縦横とも奇数なので、1列で済むはずです。 話を単純化しようとペントミノから話をはじめましたが、ここらで、本題のヘキソミノで話を進めることにします。 |
と書いたものの、もうちょっとペントミノ上で加筆修正しようと思っている内に日が過ぎて行くのでとりあえずUp
つづく