ホーム >
家族のギャラリー >
ペントミノを解く >
第6章 ヘキソミノあれこれ >
4. 1億解までのピース変化
4. 1億解までのピース変化
前節の実験で求めた１億解ですが、解のうち、１番目、１００万番目、１千万番目、１億番目の４種の解を以下に示します。
ピースは左上から下にはめ込んでいき、解が完成すると右下から剥がしながら違うピースのはめ込みを試しています。このため、箱の左側はなかなか変化せず、右側だけが変化します。
【１番目の解】
+---+ | | +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ | | | | | | | | +---+---+ +---+ +---+ +---+---+ +---+ + +---+ +---+ + | | | | | | | | | | | | | + +---+ + +---+ +---+---+---+ +---+---+---+ + + +---+ + + | | | | | | | | | | | | | | + + +---+---+ +---+ +---+ +---+---+ +---+ + +---+---+---+ | | | | | | | | | | | | + +---+---+---+---+ +---+---+---+ + + +---+---+---+ + +---+ | | | | | | | | | | + +---+---+ +---+---+---+---+---+ + +---+---+---+ +---+---+ + + | | | | | | | | | | | +---+ +---+---+---+ + +---+---+---+---+---+---+---+---+---+ + | | | | | | | | +---+---+---+---+ +---+ +---+ +---+ +---+---+ +---+---+---+ +---+ | | | | | | | | | | | + +---+---+---+---+---+---+ +---+ +---+---+ +---+ +---+---+ + | | | | | | | | | | | +---+ +---+---+ +---+---+ +---+---+---+ +---+ + +---+ +---+ + | | | | | | | | | | | + +---+ +---+ +---+---+---+ +---+---+---+---+---+---+ + + | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+【１００万番目の解】
+---+ | | +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ | | | | | | | | +---+---+ +---+ +---+ +---+---+ +---+---+ + +---+---+ + | | | | | | | | | | | + +---+ + +---+ +---+---+---+ +---+ +---+ +---+---+---+---+ + | | | | | | | | | | | | | | + + +---+---+ +---+ +---+ +---+---+ + +---+---+---+ +---+---+ | | | | | | | | | | + +---+---+---+---+ +---+---+---+ + +---+---+---+---+ + +---+ + | | | | | | | | | | | | | + +---+---+ +---+---+---+---+---+ +---+ + + +---+ + + + | | | | | | | | | | | | | +---+ +---+---+---+ + +---+ + + +---+---+ + + | | | | | | | | | | +---+---+---+---+ +---+ +---+ +---+---+---+---+---+---+ +---+ + + | | | | | ★ | | | | | + +---+---+---+---+---+---+ +---+---+---+---+---+---+ +---+---+ + + | | | | | | | | | | +---+ +---+---+ +---+---+ +---+---+ + +---+ +---+ +---+---+ | | | | | | | | | | | | | + +---+ +---+ +---+---+---+ +---+ +---+ + +---+ +---+ + | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+動いたピースは右半分の★のピースまでの17個だけ。【１千万番目の解】
+---+ | | +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ | | | | | | | +---+---+ +---+ +---+ +---+---+---+ + +---+---+---+---+---+---+ | | | | | | | | | + +---+ + +---+ +---+---+---+ +---+---+ +---+---+---+ +---+ + | | | | | | | | | | | | | | | | + + +---+---+ +---+ +---+ + +---+---+ + +---+ + + | | | | | | | | | | | | | + +---+---+---+---+ +---+ +---+---+ +---+ + + + +---+ +---+ | | | | ★ | | | | | | | + +---+---+ +---+---+---+---+ +---+ + +---+ + +---+ +---+ + | | | | | | | | | | | | | +---+ +---+---+---+ +---+ +---+ +---+ +---+---+---+---+---+ | | | | | | | | | | +---+---+---+---+ +---+ +---+ +---+---+ + + +---+ +---+ + | | | | | | | | | | | | | + +---+---+---+---+---+---+ +---+---+---+ + +---+---+ +---+ + | | | | | | | | | +---+ +---+---+ +---+---+ +---+---+ + +---+---+ + +---+---+---+ | | | | | | | | | | | | + +---+ +---+ +---+---+---+ +---+ +---+ +---+---+ + + | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+★まで動いて、ようやく２０個のピースが使われ始めた。【１億番目の解】
+---+ | | +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ | | | | | | | | +---+---+ +---+ +---+ +---+---+---+ + + +---+---+ + | | | | | | | | | | | + +---+ + +---+ +---+---+---+ +---+ + + +---+---+---+---+ | | | | | | | | | | | | | | + + +---+---+ +---+ +---+ +---+---+ +---+ + + + +---+ + | | | | | | | | | | | | | | | + +---+---+---+---+ +---+ +---+ +---+---+ +---+ + +---+ + + | | | | ★ | | | | | | | + +---+---+ +---+---+---+---+ +---+---+ + +---+---+ +---+ +---+ | | | | | | | | | | | | +---+ +---+---+---+ + +---+ + + + +---+---+---+ +---+ | | | | | | | | | | | | | +---+---+---+---+ +---+ +---+---+ + +---+ + +---+ +---+ + | | | | | | | | | | | + +---+---+---+---+---+---+ +---+ +---+ + +---+---+---+ +---+ + | | | | | | | | | | +---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+---+ + | | | | | | | | | | | | + +---+ +---+ +---+---+---+ +---+---+ +---+---+ + +---+---+ | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+動いたピースの位置は１千万番目と同じで、２０個のピースしか動いていない。
ピースが増えるに従って急速に解が増えていくことが判る。１番目と１億番目を比較して動いていないピースを切り出すと以下のようになる。
+---+---+---+---+---+---+---+---+ | | | | +---+---+ +---+ +---+ +---+ | | | | | + +---+ + +---+ +---+---+---+ | | | | | | | | + + +---+---+ +---+ +---+ | | | | + +---+---+---+---+ +---+ | | | | + +---+---+ +---+---+---+---+ | | | | | +---+ +---+---+---+ + | | | | +---+---+---+---+ +---+ +---+ | | | | | + +---+---+---+---+---+---+ +---+ | | | | +---+ +---+---+ +---+---+ +---+---+ | | | | | | | + +---+ +---+ +---+---+---+ +---+ | | | | +---+---+---+---+---+---+---+---+---+-以上の結果は第２節で試した、100万回を求める場合の最小探索数になったピースのはめ込み順序で試したものです。このため、平均的なピースの動きになっていない可能性があります。また、100万解毎に結果を出力しているので、実際に幾つピースが動いたときにどの程度の解が求まっているのかはっきりしません。
そこでもっと定量的に、動いたピースと見つかった解の関係を求めてみることにしました。そこから全解を推定してみようというわけです。次節につづく。