各ブロックの配置可能な全ケースが求まりました。下図にそれらを示します。
(3-5)収納探索
ブロック 番号1 |
ブロック 番号2 |
ブロック 番号3 |
ブロック 番号4 |
ブロック 番号5 |
ブロック 番号6 |
ブロック 番号7 |
---|---|---|---|---|---|---|
・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ |
・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | |
・・・ | ・・・ | |||||
144 | 144 | 72 | 64 | 96 | 72 | 36 |
この7個のブロックは夫々、144、144、72、64、96、72、36の配置可能ケースを持ちますがこれらの1個づつを組み合わせて立方体に納まるかを試します。きちんと納まった組合せが解答となります。
その手法を説明するために簡略化したモデルを用います。ここに、4個のブロックで配置可能なケースが夫々、2,3,2,4という架空のモデルを設定しました。
下図のように、配置していく組合せは、順位1番が1,1,1,1、2番が1,1,1,2、3番が1,1,1,3、4番が1,1,1,4、5番が繰り上がって1,1,2,1、6番が1,1,2,2、・・・、で最後が48番で2,3,2,4となります。組合せの総数は各ブロックの配置ケース数を掛け合わせたもの、即ち2X3X2X4=48となります。
収納探索手順
組合せ順位1番から順番にブロック1からブロック4を順次試します。図の組合せ順位1では、ブロック1は納まった(緑)がブロック2が納まらなかった(柿色)ことを色で表現しています。結果、回答の成否が”X"になりました。組合せ順位の2番から8番は当然納まりませんからバイパスして、次の試みは9番に移ります。ここではブロック1と2は納まりましたが3が納まりません。次の試みは13番です。ここではブロック1、2、3と納まり、組合せ順位15番のブロック4のケース3で納まりました。結果、解答の成否が"○”で解答順位”1”が記録されました。以下同じように推移して、組合せ順位27番と46番が収まり、夫々解答順位が2、3と記録されました。
実モデルでの探索
実モデルでは簡略化モデルとは異なり組合せの数が膨大になります。
その数は、144x144x72x64x96x72x36=23,776,267,862,016(23兆7762億6786万2016) これは1秒間に1回全点試したとしたら、75万年かかります。
探索手順は簡略化モデルと同じ手法です。因みに、
1番目の解答は、
組合せ順位が 513,939,384,642番(4,17,16,64,12,42,30)、
中間の4044番目の解答は、
組合せ順位が 11,885,188,548,555 番(72,142,32,4,17,13,27)、
最後の8088番目の解答は、
組合せ順位が 23,280,399,560,775番(141,144,39,49,50,2,3)
において得られました。