ヘキソミノ完全解へのシナリオ
ver. 0.05 2001/10/09 daichin@excite.co.jp
   http://hexomino.hp.infoseek.co.jp/

・Version History
 0.05 01/10/09 命題1の検討から進め方を修正、分割の手順を追加。
 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 まだまだ、矛盾だらけ、説明不足だらけですがとりあえずリリース。


第1期(01/01/27〜01/03/16)の成果 ( 詳細は ヘキソミノの掲示板 過去ログ No.1 )

 ・ 全解の推定は10の20乗から25乗程度
 ・ 全解をリニアに、しらみつぶしで解くことは時間的に困難
 ・ 全解の保存もDisk容量的に困難
 ・ 仮に保存できたとしても、全解の比較検証は困難

上記を前提とした「第2期の方針」

 ・ 複数個のピースからなる集合体を、
   (1)使用ピースの個数、
   (2)種類、
   (3)組合せの外形
  で分類し、(4)同じものが何個あるかを求める。
 ・ 情報として必要なのは、上記4つの情報であり、その中でのピースの組み合わせ方は必要ない。
 ・ 検証、追試は(4)に関して行うことで可能。

 ・ 小さな集合体同士の組み合わせを積み上げて行くことで、完全解数を求める。
 ・ この途中過程において、上記と同様その組合せ方について保存する必要はなく集合体が大きく
  なっても保存すべきデータは上記4種のみが必要、十分である。

 ・ これにより、計算時間が現実的な長さになるかは、現状ではいまだ不明。外形が同じに
  なるものがどの程度の比率あるかがポイント。


分割の手順

 命題1の検討から、 命題1をフラットに計算し保存することが既に現実的でないことが分かり、命題1は分割し求め、その都度、中央以外の部分を計算し解数を求めるように変更する。分割の階層は必要に応じて適宜分割する。(以下の分割No.それぞれ異なることになると思われる。)

 ・ 左右の空きスペースが6の倍数という制限から左右の空きスペース(ピース数)と中央での使用ピース数の組合せは以下の16通り。

 ・ この内、左右の空きピース数が異なる場合は、左側の個数が小さいもののみ残すことにより、左右反転の重複を除く。

 ・ 左右の空きピース数が同数の場合は、別途重複を除く。

分割No. 中央
1 16 3 16
2 15 4 16
3 15 5 15
4 14 5 16
5 14 6 15
6 13 6 16
7 14 7 14
8 13 7 15
9 12 7 16
10 13 8 14
11 12 8 15
12 11 8 16
13 13 9 13
14 12 9 14
15 11 9 15
16 10 9 16

分割No.1

 中央3ピースの組合せの中には、外形だけではない左右完全対称形が含まれている。その組合せに使われるピースの種類と向きは以下の10通り。

                                                     
                                                     
                                                     
                                                     
                                                     
                                                     

命題1: 中央縦一列を埋める全組合せを求める。

 命題1.1: 中央最上行(へそ)部分を埋める組合せは何通りか?

命題2:命題1の左右の残りスペースに死角がなく、6の倍数になっている組合せは何通りか?

 命題2.5: 命題2のうち、左右対象の組合せは何通りか?
       これの残りスペースは左右反転になる為、左側で使用した組合せを右側では使用しないようにカウントすることで反転重複を除く。

 命題2.6: 命題2のうち、左右反転の関係にあるものをペアにし、片方のみを残し、反転重複解を除く。
       どちらを残すかは、左側の外形が同じになる組合せを多くする様にする?(要検討)

命題3:左の縦一列を埋める組合せで死角のないものは何通りか?

 命題3.5:命題3の解のうち、同じピースの組み合わせで、かつ外形が同じものを除いた組み合わせは何通りか? またそれぞれの組み合わせの外形が同じものはそれぞれ何通りか?

命題4:命題2と3の組合せは何通りか?

命題5:命題4の残りスペースに死角がなく、6の倍数になっている組合せは何通りか?

 命題5.5:残りのスペースの最上行(最下行あるいは複数行)を注目し、その空きパターンは何通りか?

 命題5.6:命題5.5を埋める全組み合わせは何通りか?

命題6:残りスペースの形状は何通りあるか?

命題7:各残りスペースを埋める組合せは何通りか?

命題8:命題5と7でピースが重複しない組合せは何通りか?

命題9:右側に残されたスペースと同形状の解析結果を左側の結果から求める。


命題1: 中央縦一列(下図黒部分)を埋める全組合せを求める。

                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
ピース3個の例
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
ピース7個の例
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
  • [制限事項] 左側の(当然右側も)残りスペースが6の倍数であること。
  • [解析のポイント] 下記のようにピースの種類、向きに加え、横幅の数だけ平行移動も考慮に入れる必要がある。この情報をピースデータ(piece*.h)に仕込んでおく必要あり。
                                               
                                               
                                               
                                               
                                               
                                               
                                               
                                               
                                               
                                               
                                               
                                               
                                               

命題3:左の縦一列を埋める組合せで死角のないものは何通りか?

               
               
               
               
               
               
               
               
               
               
               
               
               
ピース2個の例
               
               
               
               
               
               
               
               
               
               
               
               
               
ピース8個の例
               
               
               
               
               
               
               
               
               
               
               
               
               

命題4:命題2と3の組合せは何通りか?

残りのスペースが多い例
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
残りのスペース(グレーの部分)が少ない例
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           

命題5.5:残りのスペースの最上行(最下行あるいは複数行)を注目し、その空きパターンは何通りか?

 ・下図黒色部分の幅と位置で分類。

幅が 8と5列 の例
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
幅が 0と4列 の例
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           

inserted by FC2 system