構想検討 -> 文書化 -> 図示化 -> コーディング それぞれに結構な時間がかかるので、まあ、少しずつ進めて行きます。
解数分布の大雑把な推定
縦中央線を重複境界として左右に2分割。
縦中央線の組み合わせは、1E11程度と推定。
| 中央の出っ張りに置けるピースは、35ピース中、32ピース。置けないのは左の３つ。 向きを含めると110通り。 ピース#0を置いた場合の組み合わせは1.5E9（1,462,102,922 2010/2/22） |
 |
一つの中央線組み合わせに対して、右側半分がどのピースを使うかという組み合わせが平均1E7程度、それぞれのピースの組み合わせに平均1E3。
左側は、残りのピースでの組み合わせになるので、平均1E3程度。
全解はこれらの組み合わせになるので、1E11 ｘ 1E7 ｘ 1E3 ｘ 1E3 = 1E24 となりで今までの推定の範囲に収まる。
それぞれの要素は、ピースの組み合わせにより、乗数が±2（0.01〜100倍）程度は平気でバラつくと思われることも加味して、計算時間,パーツリストの構造、サイズ等を検討する。
計算時間の推定
２分割のパーツ・リストがすべてできた状態を仮定すると、1E11(右) ｘ 1E7(左) = 1E18 の組み合わせに対して、検索して、それぞれの重みを掛け算して、その総和を取ることになります。1CPUでの1秒あたりの処理数は1E7程度になるのではと想定してます。そうすると、1E18 / 1E7 = 1E11秒・CPU = 1E6日・CPU。1000個のCPUをフルに使って3年かかることになります。
かろうじて実現可能な推定になりますが、前提に２分割パーツ・リストが完成しているということがあり、それでもこれだけの処理が必要になるということです。この後、推定するパーツ・リストの作成にはこれ以上の膨大な処理時間が必要になるはずですので、いずれにしろ、すべてうまくいったとしても１０年後の２０２０年でも厳しいだろうという話だということです。
特に、ここ数年で顕著になった消費電力に対する制限というのが非常にインパクトが大きいように思います。スパコンでさえ、消費電力が性能の指標になる時代ですから、人類にとってなんの役にも立たないこの計算の為に、多数のCPU時間（＝電力消費）を提供していただくというのは、なかなか難しい時代になりました。
３５ピースの定義に６ビット、最大８通りの向きに３ビット、最大６段の位置に３ビットで、合計１２ビット必要になり
、１６ビット変数（short）を使うと４ビット余ります。
パーツを定義する場合、複数のピース並びを定義するので、４ビットの空きを作らず圧縮して保存することも可能ですが、その後の処理を考えると、各ピース毎に１６ビット（２バイト）にするのがシンプルです。ストレージ容量はまだまだこれからも増加しそうですので、とりあえずこれで進めてみます。バイトの区切りで分ける右側のパターンも使いやすそうですが、左側のパターンでまずはコーディングしてみます。
空き ピース# 向きoffset 空き ピース# 空き 向きoffset
0 0 0 0 p p p p p p r r r o o o 0 0 p p p p p p 0 0 r r r
o o o
....0..... ....0..... ....0..... ....0..... ....0..... ....0..... ....11111. ...222221. .333332... ...34444.. ..8855544. ..8888555. |
000000 001 000 | 一番はじめに求まる左図のパーツは、このように１４バイトで表現できます。 |
....0..... ....0*.... ....0*.... ....0*.... ....0*.... ....0*.... ....11111. ........1. |
....v..... ..8888555. ..8855544. ...34444.. .333332*.. ...222221. ....11111. |
上と下を半分に分けると左の２つの分割され、*印の部分を含めて、現在考えている最小サイズのパーツになります。 右側のパターンは分割方法の検討の時には想定していなかったパターンです。このように境界が隣り合わせていない場合もあることを考慮に入れる必要が出てきました。 |
|
|
|
処理フロー nPattern = 0; for (iCtr = 0; iCtr < N_of_CtrParts; iCtr++) { トップレベルはこれだけになります。getPatternsの中で、右と左の２分割パーツがすでにパーツリストにあれば、それらの組み合わせ数を乗算して終わり。パーツリストにない場合は、４分割リストを検索、なければ８分割、それでもなければ最小パーツへと降りて行って、必要なパーツリストだけを作成しながら、解を求めて行きます。 最初は、すべての階層のパーツリストを作成しながらの処理になりますが、少しずつ既存のパーツリストの再利用率が高くなっていき、解を求める時間が加速度的に早くなっていくことを予想していますが、それが現実的に意味のある時間軸に乗ってくるのかどうかは、かなり怪しいというのが、過去の試行で学んだことです・・・ 複数の方の協力がいただけるような状況になった場合には、パーツリストをネット上に置き、それとローカルのキャッシュとの同期を取りながら進めるような以下プロセスも必要になります。 パーツリストが どこかでフローチャートに整理しようと思いますが、いつになるか・・・ |
|
|
|
バイナリデータの図示化 各階層パーツリストは、境界上のパーツ並びをバイナリデータで保存しますので、いったいどんな形の組み合わせになっているのかは、人間が見てもわかりません。それではつまらないし、バグも見つけられないので、図示化のツールが必要になります。 とりあえず、上での説明に必要な最小機能でザクっと作ったものがこれ （まだピース番号１０以上に対応してないとか、データをmain（）にベタ書きしてるとか、上下位置を計算で求めず数値を入れてるとかの未完成品です） |
・Version History
0.32 10/02/24 詰める順番を左上から、右上に変更、各章追記、バイナリデータの図示化追加
0.31 10/02/22 計算時間の推定、ピースの数値表現、処理フロー書きかけ
0.30 10/02/20 部分解への分割方法の検討ver.0.15に合わせて全面改訂初稿
0.20 02/12/24 再度、仕切りなおし。部分解の高速化を進めるのはそのままだが、分割方法を
使用ピースの種類からサブパーツの形状に変更。
0.10 02/12/11 原点の「パズルのプログラミングを楽しもう」に戻って、再出発
0.05 01/10/09 ヘキソミノ完全解へのシナリオVer.
0.05
0.04 01/08/24 命題1.1、2.5、2.6の追加。
0.03 01/08/23 第1期の成果、第2期の方針を追加。
0.02 01/08/08 早速命題3.5、5.5、5.6の追加。
0.01 01/08/05 初稿 まだまだ、矛盾だらけ、説明不足だらけですがとりあえずリリース。