ヘキソミノ完全解へのシナリオ | ||||||||||||||||||||||||||||||||||||||||
ver. 0.34 2010/03/03 daichinアットexcite.co.jp | ||||||||||||||||||||||||||||||||||||||||
http://hexomino.hp.infoseek.co.jp/ | ||||||||||||||||||||||||||||||||||||||||
部分解への分割方法の検討ver.0.15に合わせて全面改訂になりますが、まだ当分落書き、備忘録レベルです。 構想検討 -> 文書化 -> 図示化 -> コーディング それぞれに結構な時間がかかるので、まあ、少しずつ進めて行きます。 |
||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||
解数分布の大雑把な推定 縦中央線を重複境界として左右に2分割。 縦中央線の組み合わせは、1E11程度と推定。
一つの中央線組み合わせに対して、右側半分がどのピースを使うかという組み合わせが平均1E7程度、それぞれのピースの組み合わせに平均1E3。 左側は、残りのピースでの組み合わせになるので、平均1E3程度。 全解はこれらの組み合わせになるので、1E11 x 1E7 x 1E3 x 1E3 = 1E24 となりで今までの推定の範囲に収まる。 それぞれの要素は、ピースの組み合わせにより、乗数が±2(0.01〜100倍)程度は平気でバラつくと思われることも加味して、計算時間,パーツリストの構造、サイズ等を検討する。 計算時間の推定 2分割のパーツ・リストがすべてできた状態を仮定すると、1E11(右) x 1E7(左) = 1E18 の組み合わせに対して、検索して、それぞれの重みを掛け算して、その総和を取ることになります。1CPUでの1秒あたりの処理数は1E7程度になるのではと想定してます。そうすると、1E18 / 1E7 = 1E11秒・CPU = 1E6日・CPU。1000個のCPUをフルに使って3年かかることになります。 かろうじて実現可能な推定になりますが、前提に2分割パーツ・リストが完成しているということがあり、それでもこれだけの処理が必要になるということです。この後、推定するパーツ・リストの作成にはこれ以上の膨大な処理時間が必要になるはずですので、いずれにしろ、すべてうまくいったとしても10年後の2020年でも厳しいだろうという話だということです。 特に、ここ数年で顕著になった消費電力に対する制限というのが非常にインパクトが大きいように思います。スパコンでさえ、消費電力が性能の指標になる時代ですから、人類にとってなんの役にも立たないこの計算の為に、多数のCPU時間(=電力消費)を提供していただくというのは、なかなか難しい時代になりました。 |
||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||
ピースの数値表現 35ピースの定義に6ビット、最大8通りの向きに3ビット、最大6段の位置に3ビットで、合計12ビット必要になり
、16ビット変数(short)を使うと4ビット余ります。
パーツを定義する場合、複数のピース並びを定義するので、4ビットの空きを作らず圧縮して保存することも可能ですが、その後の処理を考えると、各ピース毎に16ビット(2バイト)にするのがシンプルです。ストレージ容量はまだまだこれからも増加しそうですので、とりあえずこれで進めてみます。バイトの区切りで分ける右側のパターンも使いやすそうですが、左側のパターンでまずはコーディングしてみます。
|
||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||
・Version History 0.34 10/03/03
下層パーツの組み合わせで4分割パーツ1個完成。検証用4分割パーツ結果 0.20 02/12/24 再度、仕切りなおし。部分解の高速化を進めるのはそのままだが、分割方法を
|
||||||||||||||||||||||||||||||||||||||||