ホーム > 家族のギャラリー > ペントミノを解く > 第6章 ヘキソミノあれこれ > 5. 全解の推定

5. 全解の推定

最終的な全解を推定するために、動いた（使った）ピースと見つかった解の関係を定量的に調べてみました。前節で、17個のピースで100万解、20個のピースで1億回程度であることがわかりましたが、もっと正確にピースの個数と解の数を求めようというものです。プログラムに細工をして、ピースの動きと解数を記録するようにしました。

全解を推定するためには特殊なピースの並びでは上手くいかないので、第２節で試みた乱数によるピーステーブルのシャッフルと探索数の関係から、平均的な探索数になる並びを方を選んでみました。平均的なもの５種類と、100万解が一番早く見つかった並び、さらに解がなかなか見つからない並びの計７種類で測定しました。

計算時間が膨大にかかるので、取り敢えず19個迄のピースの組合せで求まる解の推移を計算したものが図5-1です。縦軸が解数、横軸が使ったピース数です。系列１の赤い線が100万解が一番早く見つかったピーステーブルの並びで、系列２のマゼンタが解がなかなか見つからないピーステーブル、他の５本の線が平均的な探索数になったものです。結構ばらついた結果になり、傾向を掴むにはいいかなと思っています。

これらの線の平均あたりを伸ばしていくと、35個のピースで求まる解の数が推定できそうです。と、いっても全体の1/4程度しかプロットできていないので推定は難しいです。そこを無理矢理伸ばすと35個では10の21乗程度になりそうです。

図5-1 使用ピースと見つかった解数の関係

使用ピースを増やしていくと７つの線が徐々に収束していき精度が上がると思うのですが、ピースがひとつ増えるたびに計算時間が級数的に増えるので難しいです。取り敢えず一つ増やした20個まではやってみようと思っています。